{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Subsequence Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大子序列的分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>&nbsp;，两者长度都是&nbsp;<code>n</code>&nbsp;，再给你一个正整数&nbsp;<code>k</code>&nbsp;。你必须从&nbsp;<code>nums1</code>&nbsp;中选一个长度为 <code>k</code>&nbsp;的 <strong>子序列</strong>&nbsp;对应的下标。</p>\n",
    "\n",
    "<p>对于选择的下标&nbsp;<code>i<sub>0</sub></code>&nbsp;，<code>i<sub>1</sub></code>&nbsp;，...，&nbsp;<code>i<sub>k - 1</sub></code>&nbsp;，你的&nbsp;<strong>分数</strong>&nbsp;定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums1</code>&nbsp;中下标对应元素求和，乘以&nbsp;<code>nums2</code>&nbsp;中下标对应元素的&nbsp;<strong>最小值</strong>&nbsp;。</li>\n",
    "\t<li>用公式表示：&nbsp;<code>(nums1[i<sub>0</sub>] + nums1[i<sub>1</sub>] +...+ nums1[i<sub>k - 1</sub>]) * min(nums2[i<sub>0</sub>] , nums2[i<sub>1</sub>], ... ,nums2[i<sub>k - 1</sub>])</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <strong>最大</strong>&nbsp;可能的分数。</p>\n",
    "\n",
    "<p>一个数组的 <strong>子序列</strong>&nbsp;下标是集合&nbsp;<code>{0, 1, ..., n-1}</code>&nbsp;中删除若干元素得到的剩余集合，也可以不删除任何元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3\n",
    "<b>输出：</b>12\n",
    "<b>解释：</b>\n",
    "四个可能的子序列分数为：\n",
    "- 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。\n",
    "- 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。\n",
    "- 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。\n",
    "- 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。\n",
    "所以最大分数为 12 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1\n",
    "<b>输出：</b>30\n",
    "<b>解释：</b>\n",
    "选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-subsequence-score](https://leetcode.cn/problems/maximum-subsequence-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-subsequence-score](https://leetcode.cn/problems/maximum-subsequence-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,3,2]\\n[2,1,3,4]\\n3', '[4,2,3,1,1]\\n[7,5,10,9,6]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        left, right = 0, len(tokens)-1\n",
    "        maxScore = score = 0\n",
    "        while left <= right:\n",
    "            if power < tokens[left] and score <= 0:\n",
    "                return maxScore\n",
    "            else:\n",
    "                if power >= tokens[left]:\n",
    "                    power -= tokens[left]\n",
    "                    left += 1\n",
    "                    maxScore = max(maxScore, score := score + 1)\n",
    "                else:\n",
    "                    while score > 0 and power < tokens[left]:\n",
    "                        power += tokens[right]\n",
    "                        right -= 1\n",
    "                        score -= 1\n",
    "        return maxScore\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        psum = [0] * (n + 1)\n",
    "        for i in range(n): psum[i+1] = psum[i] + tokens[i]\n",
    "\n",
    "        def f(L, R, P):\n",
    "            l, r = L, R + 1\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) // 2\n",
    "                if psum[mid] - psum[L] <= P:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l - L\n",
    "\n",
    "        l, r = 0, n\n",
    "        maxScore = 0\n",
    "        while l < r:\n",
    "            maxScore = max(maxScore, f(l, r, power))\n",
    "            if power >= tokens[l]:\n",
    "                power = power - tokens[l] + tokens[r-1]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return maxScore\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            cnt = 0\n",
    "            for j in range(i):\n",
    "                if s[j] == '0':\n",
    "                    cnt += 1\n",
    "            for j in range(i, n):\n",
    "                if s[j] == '1':\n",
    "                    cnt += 1\n",
    "            ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:n].count(\"0\")+s[n:].count(\"1\") for n in range(1,len(s)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans = s[:1].count('0') + s[1:].count('1')\n",
    "        for i in range(1, len(s)):\n",
    "            score = s[:i].count('0') + s[i:].count('1')\n",
    "            ans = max(ans, score)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count(\"0\")+s[i:].count(\"1\") for i in range(1,len(s))) # 至少从s[1]位开始分割"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        total_sum = 0\n",
    "        for index in range(1,len(s)):\n",
    "            left_len = s[:index].count('0')\n",
    "            right_len = s[index:].count('1')\n",
    "            total_sum = max(total_sum, left_len+right_len)\n",
    "        return total_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(s)):\n",
    "            step=0\n",
    "            for j in range(i):\n",
    "                if int(s[j])==0 :step+=1\n",
    "            for k in range(i,len(s)):\n",
    "                if int(s[k])==1 :step+=1\n",
    "            if step>=ans :\n",
    "                ans=step\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        left = ''\n",
    "        right = ''\n",
    "        temp = 0\n",
    "        max_t = 0\n",
    "        for i in range(1 , l):\n",
    "            left = s[0 : i]\n",
    "            right = s[i :]\n",
    "            temp =  left.count('0') + right.count('1')\n",
    "            if temp > max_t:\n",
    "                max_t = temp\n",
    "        return max_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        str1,str2=s[0],s[1:]\n",
    "        ans=0 if str1=='1' else 1\n",
    "        for c in str2:\n",
    "            if c=='1':\n",
    "                ans+=1\n",
    "        res=ans\n",
    "        for c in str2[:-1]:\n",
    "            if c=='0':\n",
    "                ans+=1\n",
    "            else:\n",
    "                ans-=1\n",
    "            if res<ans:\n",
    "                res=ans\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n = 0\n",
    "        for i in range(1,len(s)):\n",
    "            left_s = s[:i]\n",
    "            right_s = s[i:]\n",
    "            val = left_s.count(\"0\") + right_s.count(\"1\")\n",
    "            if val > n:\n",
    "                n = val\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        one,zero = s.count('1'), 0\n",
    "        res = 0\n",
    "        for i in s[:-1]:\n",
    "            if i == '0':\n",
    "                zero += 1\n",
    "            else:\n",
    "                one -= 1\n",
    "            if zero + one > res:\n",
    "                res = zero + one\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        i = 1\n",
    "        sums = 0\n",
    "        while i < len(s):\n",
    "            int2 = int1  = 0\n",
    "            for j in s[0:i]:\n",
    "                if int(j) == 0:\n",
    "                    int1 += 1\n",
    "            for n in s[i:len(s)]:\n",
    "                int2 += int(n)\n",
    "            if int1 == len(s):\n",
    "                return 1\n",
    "            elif int1 + int2 > sums:\n",
    "                sums = int1 + int2\n",
    "            i += 1\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        k=1\n",
    "        ans=0\n",
    "        while k<n:\n",
    "            q=s[0:k]\n",
    "            h=s[k:n+1]\n",
    "            k+=1\n",
    "            i=q.count('0')\n",
    "            j=h.count('1')\n",
    "            ans=max(ans,i+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        i = 1\n",
    "        n = len(s)\n",
    "        result = []\n",
    "        for i in range(1, n):\n",
    "            left_str = s[: i]\n",
    "            right_str = s[i : n]\n",
    "            num = left_str.count(\"0\") + right_str.count(\"1\")\n",
    "            result.append(num)\n",
    "            \n",
    "        return max(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            left_str = s[0:i+1]\n",
    "            right_str = s[i+1:n+1]\n",
    "            #print(left_str,right_str)\n",
    "            left_str_cnt0 = 0\n",
    "            right_str_cnt1 = 0\n",
    "            for l in range(len(left_str)):\n",
    "                if left_str[l] == '0':\n",
    "                    left_str_cnt0 += 1\n",
    "            for k in range(len(right_str)):\n",
    "                if right_str[k] == '1':\n",
    "                    right_str_cnt1 += 1\n",
    "            res_tmp = left_str_cnt0 + right_str_cnt1\n",
    "            #print(res_tmp)\n",
    "            if res_tmp > res:\n",
    "                res = res_tmp\n",
    "                #print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0')+s[i:].count('1') for i in range(1,len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0') + s[i:].count('1') for i in range(1, len(s)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        k = 0; k_ = 0\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i] == \"1\":\n",
    "                k+=1\n",
    "            else:\n",
    "                k_+=1\n",
    "        # k为1 k_为0\n",
    "\n",
    "        ans = 0\n",
    "        o = 0\n",
    "        for i in range(0,len(s)-1):\n",
    "            if s[i] == \"1\":\n",
    "                k -=1\n",
    "            else:\n",
    "                o+=1\n",
    "            ans = max(ans,o+k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        total_sum = 0\n",
    "        for index in range(1,len(s)):\n",
    "            left_len = 0\n",
    "            right_len = 0\n",
    "            for left_index in range(index):\n",
    "                # print(left_index)\n",
    "                if s[left_index] == '0':\n",
    "                    left_len+=1\n",
    "            for right_index in range(index,len(s)):\n",
    "                # print(right_index)\n",
    "                if s[right_index] == '1':\n",
    "                    right_len+=1\n",
    "            total_sum = max(total_sum, left_len+right_len)\n",
    "        return total_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        # 暴力法\n",
    "        lenth = len(s)\n",
    "        score = 0\n",
    "        for i in range(1,lenth):\n",
    "            left = s[:i]\n",
    "            right = s[i:]\n",
    "            score = max(left.count('0') + right.count('1'),score)\n",
    "        return score\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        result=0\n",
    "        n=len(s)\n",
    "        for i in range(1,n):\n",
    "            x1=s[:i]\n",
    "            x2=s[i:]\n",
    "            single=x1.count(\"0\")+x2.count(\"1\")\n",
    "            if single>result:\n",
    "                result=single\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(s)):\n",
    "            ans=max(ans,s[0:i].count('0')+s[i:len(s)].count('1'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        one = 0\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                one += 1\n",
    "        lzero,lone = 0,0\n",
    "        res = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == '0':\n",
    "                lzero += 1\n",
    "            else:\n",
    "                lone += 1\n",
    "            res = max(res,lzero + (one - lone))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        maxx = 0\n",
    "        for i in range(1, len(s)):\n",
    "            left = s[:i]\n",
    "            right = s[i:]\n",
    "            l0 = left.count('0')\n",
    "            r1 = right.count('1')\n",
    "            if l0 + r1 >= maxx:\n",
    "                maxx = l0 + r1\n",
    "        return maxx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "         n, presum, ans = len(s), 0, -inf\n",
    "         for i in range(n):\n",
    "            if i and (cur := presum * 2 - i) > ans:\n",
    "                ans = cur\n",
    "            presum += s[i] == \"0\"\n",
    "         return ans + n - presum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)):\n",
    "            ls, rs = \"\", \"\"\n",
    "            x = 0\n",
    "            ls = s[:i]\n",
    "            rs = s[i:]\n",
    "            for j in ls:\n",
    "                if j == \"0\":\n",
    "                    x += 1\n",
    "            for k in rs:\n",
    "                if k == \"1\":\n",
    "                    x += 1\n",
    "            ans = x if x > ans else ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0')+s[i:].count('1') for i in range(1,len(s)))\n",
    "\n",
    "        #s[:i]表示从最开始到i-1\n",
    "        #s[i:]表示从i到最后\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n, presum, ans = len(s), 0, -inf\n",
    "        for i in range(n):\n",
    "            # cur = presum + (n - i - final_presum + presum) = presum * 2 - i + (n - final_presum)\n",
    "            if i and (cur := presum * 2 - i) > ans:\n",
    "                ans = cur\n",
    "            presum += s[i] == \"0\"\n",
    "        return ans + n - presum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count(\"0\")+s[i:].count(\"1\") for i in range(1,len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0') + s[i:].count('1') for i in range(1, len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        sub_left = \"0\"\n",
    "        sub_right = \"1\"\n",
    "        a=[]\n",
    "        for i in range(1, n):\n",
    "            left_half = s[0:i]\n",
    "            right_half = s[i:n]\n",
    "            sum_count = left_half.count(sub_left) + right_half.count(sub_right)\n",
    "            a.append(sum_count)\n",
    "        return max(a)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        score = list()  \n",
    "        for i in range(1,len(s)):\n",
    "            a = s[:i].count('0')\n",
    "            b = s[i:].count('1')\n",
    "            c = a + b\n",
    "            score.append(c)\n",
    "        return max(score)\n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        total0 = 0\n",
    "        total1 = 0\n",
    "        for i in s:\n",
    "            if i == \"0\":\n",
    "                total0 += 1\n",
    "            else:\n",
    "                total1 += 1\n",
    "        start=0\n",
    "        left = 0\n",
    "        right = total1\n",
    "        res = 0\n",
    "        while start<len(s)-1:\n",
    "            if s[start] == \"0\":\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "            start += 1\n",
    "            res = max(res,left+right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        cnt_map = collections.Counter(s)\n",
    "        zero_cnt, one_cnt = 0, 0\n",
    "        score = 0\n",
    "        for c in s[:-1]:\n",
    "            if c == '0':\n",
    "                zero_cnt += 1\n",
    "            else:\n",
    "                one_cnt += 1\n",
    "            score = max(score, zero_cnt + cnt_map.get('1', 0) - one_cnt)\n",
    "        return score\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        sum=0\n",
    "        ans=0\n",
    "        for i in range(n-1):\n",
    "           ans=max(ans,s[:i+1].count('0')+s[i+1:].count('1'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        num_of_0 = s.count('0')\n",
    "        num_of_1 = s.count('1')\n",
    "\n",
    "        left_0 = 0\n",
    "        left_1 = 0\n",
    "\n",
    "        score = 0\n",
    "        \n",
    "        for i in range(0, len(s)-1):\n",
    "            if s[i] == '0':\n",
    "                left_0 += 1\n",
    "            else:\n",
    "                left_1 += 1\n",
    "            \n",
    "            right_1 = num_of_1 - left_1\n",
    "            if left_0 + right_1 > score:\n",
    "                score = left_0 + right_1\n",
    "        \n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, string: str) -> int:\n",
    "        left = int(string[0] == '0')\n",
    "        right = sum(1 for x in string[1:] if x == '1')\n",
    "        score = left + right\n",
    "        for i in range(1, len(string) - 1):\n",
    "            if string[i] == '0':\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "            if left + right > score:\n",
    "                score = left + right\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)-1):\n",
    "            s_l = s[:i+1]\n",
    "            s_r = s[i+1:]\n",
    "            s_l_0 = 0\n",
    "            s_r_1 = 0\n",
    "            for x in s_l:\n",
    "                if x == \"0\":\n",
    "                    s_l_0 += 1\n",
    "            for y in s_r:\n",
    "                if y == \"1\":\n",
    "                    s_r_1 += 1\n",
    "            number = s_l_0 + s_r_1\n",
    "            if number > ans:\n",
    "                ans = number\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max([2*s[:i].count('0')+s.count('1')-i for i in range(1,len(s))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n = 1\n",
    "        res = []\n",
    "        left = []\n",
    "        right = []\n",
    "        while n < len(s):\n",
    "            left = s[:n]\n",
    "            right = s[n:]\n",
    "            i = left.count(\"0\") + right.count(\"1\")\n",
    "            res.append(int(i))\n",
    "            n += 1\n",
    "        \n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        k = i = 1\n",
    "        sums = 0\n",
    "        while k < len(s):\n",
    "            int2 = int1  = 0\n",
    "            for j in s[0:i]:\n",
    "                if int(j) == 0:\n",
    "                    int1 += 1\n",
    "            for n in s[i:len(s)]:\n",
    "                int2 += int(n)\n",
    "            if int1 == len(s):\n",
    "                return 1\n",
    "            elif int1 + int2 > sums:\n",
    "                sums = int1 + int2\n",
    "            k += 1\n",
    "            i += 1\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        a = 0\n",
    "        sums = 0\n",
    "        maxx = 0\n",
    "        for i in range(len(s)-1):\n",
    "            a = sum([y for x,y in collections.Counter(s[:i+1]).items() if x=='0'])\n",
    "            a += sum([y for x,y in collections.Counter(s[i+1:]).items() if x=='1'])\n",
    "            maxx = max(maxx , a)\n",
    "        return maxx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        points = []\n",
    "        for i in range(1,len(s)):\n",
    "            a = s[:i].count(\"0\")\n",
    "            b = s[i:].count(\"1\")\n",
    "            x = a+b\n",
    "            points.append(x)\n",
    "        return max(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        total_sum = 0\n",
    "        start_index = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 0:\n",
    "                start_index+=1\n",
    "        if start_index == 0:\n",
    "            start_index = 1\n",
    "        if start_index == len(s)-1:\n",
    "            start_index = len(s)-2\n",
    "        for index in range(1,len(s)):\n",
    "            left_len = 0\n",
    "            right_len = 0\n",
    "            for left_index in range(index):\n",
    "                # print(left_index)\n",
    "                if s[left_index] == '0':\n",
    "                    left_len+=1\n",
    "            for right_index in range(index,len(s)):\n",
    "                # print(right_index)\n",
    "                if s[right_index] == '1':\n",
    "                    right_len+=1\n",
    "            if total_sum < left_len + right_len:\n",
    "                total_sum = left_len + right_len\n",
    "        return total_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count(\"0\")+s[i:].count(\"1\") for i in range (1,len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        A = []\n",
    "        for i in range(1,len(s)):\n",
    "            L = s[:i]\n",
    "            R = s[i:]\n",
    "            A.append(L.count('0')+R.count('1'))\n",
    "        return max(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        count_1 = s.count('1')\n",
    "        return max([2*s[:i].count('0')+count_1-i for i in range(1,len(s))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        max_score=0\n",
    "        for i in range(n-1):\n",
    "            leftcount=s[:i+1].count('0')\n",
    "            rightcount=s[i+1:].count('1')\n",
    "            score=leftcount+rightcount\n",
    "            if score>max_score:\n",
    "                max_score=score\n",
    "            else:\n",
    "                max_score\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        if s[0]=='0':left=1\n",
    "        else : left=0\n",
    "        right = s[1:].count('1')\n",
    "        res = left + right\n",
    "        for p in range(1,len(s)-1):\n",
    "            if s[p]=='0': left +=1\n",
    "            else: right -=1\n",
    "            if left+right>res:res=left+right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "      return max(s[:i].count('0') + s[i:].count('1') for i in range(1, len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        def findone(nums):\n",
    "            ones=0\n",
    "            for num in nums:\n",
    "                if num == '1':\n",
    "                    ones +=1\n",
    "            return ones\n",
    "        res=0\n",
    "        for i in range(1,len(s)):\n",
    "            right=findone(s[i:])\n",
    "            left=i-findone(s)+right\n",
    "            temp=right+left\n",
    "            res=max(res,temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        sn = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                sn += 1\n",
    "        cnt0, cnt1 = 0, sn\n",
    "        for i in range(n-1):\n",
    "            if s[i] == '0':\n",
    "                cnt0 += 1\n",
    "            else:\n",
    "                cnt1 -= 1\n",
    "            ans = max(ans, cnt0+cnt1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        list=[]\n",
    "        for i in range(1,len(s)):\n",
    "            score=0 \n",
    "            for j in s[0:i]:\n",
    "                if j == \"0\":\n",
    "                    score += 1\n",
    "            for j in s[i:len(s)+1]:\n",
    "                if j == \"1\":\n",
    "                    score += 1\n",
    "            list.append(score)\n",
    "        return max(list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans = score = (s[0] == '0') + s[1:].count('1')\n",
    "        for c in s[1:-1]:\n",
    "            score += 1 if c == '0' else -1\n",
    "            ans = max(ans, score)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        one = s.count('1')\n",
    "        zero=0\n",
    "        mcount=0\n",
    "        for i in s[:-1]:\n",
    "            if i =='1':\n",
    "                one-=1\n",
    "            elif i=='0':\n",
    "                zero+=1\n",
    "            mcount=max(mcount,zero+one)\n",
    "        return mcount\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "\n",
    "        a=[]\n",
    "        for i in range(1,len(s)):\n",
    "            a.append(s[:i].count('0')+s[i:].count('1'))\n",
    "        print(a)\n",
    "        return max(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0')+s[i:].count('1')for i in range(1,len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n=[int(digit) for digit in s]\n",
    "        record=n.copy()\n",
    "        for i in range(len(n)):\n",
    "            n_new=n[:(i+1)]\n",
    "            count_of_zeros = n_new.count(0)\n",
    "            count_of_ones = n_new.count(1)\n",
    "            record[i]=count_of_zeros-count_of_ones\n",
    "        max_index=record.index(max(record))\n",
    "        if max_index<len(record)-1:\n",
    "            index=max_index+1\n",
    "        else:\n",
    "            index=max_index\n",
    "\n",
    "        n_reslut=n[:index]\n",
    "        n_result2=n[index:]\n",
    "        return n_reslut.count(0)+n_result2.count(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        a = Counter(s)\n",
    "        l,r = 0,a['1']\n",
    "        ans = 0\n",
    "        for i in s[:len(s)-1]:\n",
    "            if i == '0':\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            ans = max(ans,l+r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[: i].count('0') + s[i: ].count('1') for i in range(1, len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans = score = (s[0] == '0') + s[1:].count('1')\n",
    "        for c in s[1:-1]:\n",
    "            score += 1 if c == '0' else -1\n",
    "            ans = max(ans, score)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0')+s[i:].count('1') for i in range(1,len(s)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        lists = list(s)\n",
    "        sum=0\n",
    "        if s=='11' or s=='00' :\n",
    "            return 1\n",
    "        elif s=='01':\n",
    "            return 2    \n",
    "        elif s=='10':\n",
    "            return 0\n",
    "        else:        \n",
    "         for i in range(1,len(lists)):\n",
    "            str1 = lists[:i]\n",
    "            str2 = lists[i:]\n",
    "            a = str1.count('0')\n",
    "            b = str2.count('1')\n",
    "            if (a+b)>sum:\n",
    "                sum=a+b\n",
    "         return sum        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0') + s[i:].count('1') for i in range(1, len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans=score=(s[0]=='0')+s[1:].count('1')\n",
    "        for c in s[1:-1]:\n",
    "            score +=1 if c==\"0\" else -1\n",
    "            ans=max(ans,score)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        return max(s[:i].count('0') + s[i:].count('1') for i in range(1, len(s)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,len(s)):\n",
    "            l = s[:i].count('0')\n",
    "            r = s[i:].count('1')\n",
    "            ans = max(ans, l+r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        n, presum, ans = len(s), 0, -inf\n",
    "        for i in range(n):\n",
    "            # cur = presum + (n - i - final_presum + presum) = presum * 2 - i + (n - final_presum)\n",
    "            if i and (cur := presum * 2 - i) > ans:\n",
    "                ans = cur\n",
    "            presum += s[i] == \"0\"\n",
    "        return ans + n - presum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        s_len = len(s)\n",
    "\n",
    "        s_max = 0\n",
    "\n",
    "        for i in range(1, s_len):\n",
    "            a = 0\n",
    "            b = 0\n",
    "            for j in range(0, s_len):\n",
    "                if j < i and s[j] == '0':\n",
    "                    a += 1\n",
    "                if j >= i and s[j] == '1':\n",
    "                    b += 1\n",
    "\n",
    "                s_max = max(s_max, a + b)\n",
    "\n",
    "\n",
    "        return s_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        s = [int(si) for si in list(s)]\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)):\n",
    "            l = sum([1^items for items in s[:i]])\n",
    "            print(s[:i],s[i:])\n",
    "            r = sum(s[i:])\n",
    "            if l + r > ans:\n",
    "                ans = l + r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        numbers_str=[*s]\n",
    "        max=0\n",
    "       \n",
    "        for y in range(len(numbers_str)):\n",
    "            counter_0=0\n",
    "            counter_1=0\n",
    "            if y==0:\n",
    "                max=0\n",
    "            else:\n",
    "                \n",
    "                for str_ in numbers_str[:y]:\n",
    "                    if str_=='0':\n",
    "                     counter_0+=1\n",
    "                    \n",
    "                for str_ in numbers_str[y:]:\n",
    "                    if str_=='1':\n",
    "                     counter_1+=1\n",
    "                \n",
    "                if counter_1+counter_0>max:\n",
    "                    max=counter_1+counter_0\n",
    "                    \n",
    "        return max\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        # if len(s) == 2:\n",
    "        #     l = 1 if s[0] == \"0\" else 0\n",
    "        #     r = 1 if s[1] == \"1\" else 0\n",
    "        #     return l+r\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)):\n",
    "            l = Counter(s[:i])[\"0\"]\n",
    "            r = Counter(s[i:])[\"1\"]\n",
    "            ans = max(ans, l + r)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, s: str) -> int:\n",
    "        ans=0\n",
    "        #ans = float(\"-inf\")\n",
    "        for i in range(1, len(s)):\n",
    "            ans = max(ans, s[:i].count('0') + s[i:].count('1'))\n",
    "        return ans\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        mNum = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(i, j, mIndex):\n",
    "            multiplier = multipliers[mIndex]\n",
    "            if mIndex == mNum-1:\n",
    "                return max(multiplier*nums[i], multiplier*nums[j])\n",
    "            leftScore = nums[i]\n",
    "            maxScore = leftScore*multiplier+dfs(i+1, j, mIndex+1)\n",
    "            rightScore = nums[j]\n",
    "            maxScore = max(maxScore, rightScore*multiplier+dfs(i, j-1, mIndex+1))\n",
    "            return maxScore\n",
    "        return dfs(0, len(nums)-1, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = right = k\n",
    "        maxScore = 0\n",
    "        while True:\n",
    "            while right < n and nums[right] >= nums[k]:\n",
    "                right += 1\n",
    "            while left >= 0 and nums[left] >= nums[k]:\n",
    "                left -= 1\n",
    "            maxScore = max(nums[k] * (right - left - 1), maxScore)\n",
    "            if left < 0 and right >= n:\n",
    "                return maxScore\n",
    "            if left < 0:\n",
    "                nums[k] = nums[right]\n",
    "            elif right >= n:\n",
    "                nums[k] = nums[left]\n",
    "            else:\n",
    "                nums[k] = max(nums[left], nums[right])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        prevSmaller = [-1] * n\n",
    "        nextSmaller = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] < nums[stack[-1]]:\n",
    "                nextSmaller[stack.pop()] = i\n",
    "            if stack:\n",
    "                prevSmaller[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        maxScore = 0\n",
    "        for i in range(n):\n",
    "            if prevSmaller[i] + 1 <= k <= nextSmaller[i] - 1:\n",
    "                maxScore = max(nums[i] * (nextSmaller[i] - prevSmaller[i] - 1), maxScore)\n",
    "        return maxScore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        m = len(words)\n",
    "        ans = 0\n",
    "        C=Counter(letters)\n",
    "        for i in range(1,1<<m):\n",
    "            wordCount=defaultdict(int)\n",
    "            for j in range(m):\n",
    "                if (i & (1<<j)) ==0:\n",
    "                    continue\n",
    "                for k in words[j]:\n",
    "                    wordCount[k] +=1\n",
    "            ok = True\n",
    "            sum = 0\n",
    "            for  j in range(26):\n",
    "                sum += score[j] * wordCount[chr(ord('a')+j)]\n",
    "                ok = ok and (wordCount[chr(ord('a')+j)] <= C[chr(ord('a')+j)])\n",
    "            if ok :\n",
    "                ans = max(ans,sum)\n",
    "        return ans \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        #copy zero\n",
    "        def dfs(i,n,cur):\n",
    "            if i ==n:\n",
    "                return 0\n",
    "            \n",
    "            ret = dfs(i+1,n,cur)\n",
    "            ithletter = collections.Counter(words[i])\n",
    "            check = all(cur[k]>= v for k,v in ithletter.items())\n",
    "            if check:\n",
    "                ithscore = sum(score[ord(k)-97]*v for k, v in ithletter.items() )\n",
    "                cur -= ithletter\n",
    "                ret = max(ret,ithscore+ dfs(i+1,n,cur))\n",
    "                cur += ithletter\n",
    "            return ret\n",
    "        \n",
    "        n = len(words)\n",
    "        cletter = collections.Counter(letters)\n",
    "        return dfs(0,n,cletter)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        self.ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(total, curPos, left):\n",
    "            if curPos == len(words):\n",
    "                self.ans = max(self.ans, total)\n",
    "                return\n",
    "            dfs(total, curPos+1, left)\n",
    "            if Counter(words[curPos]) <= left:\n",
    "                addtion = sum([score[n] for n in words[curPos]])\n",
    "                dfs(total + addtion, curPos+1, left - Counter(words[curPos]))\n",
    "        dfs(0, 0, left)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "       def dfs(i: int, j: int) -> None:\n",
    "          if i == n:\n",
    "             nonlocal res\n",
    "             res = max(res, j)\n",
    "             return\n",
    "          # 不选 \n",
    "          dfs(i + 1, j)\n",
    "          # 选\n",
    "          cur = [0] * 26\n",
    "          for c in words[i]:\n",
    "             cur[ord(c) - ord('a')] += 1\n",
    "          if all(a >= b for a, b in zip(cnts, cur)):\n",
    "             s = 0\n",
    "             for k in range(26):\n",
    "                s += cur[k] * score[k]\n",
    "                cnts[k] -= cur[k]\n",
    "             dfs(i + 1, j + s)\n",
    "             for k in range(26):\n",
    "                cnts[k] += cur[k]\n",
    "       n = len(words)\n",
    "       cnts = [0] * 26\n",
    "       for c in letters:\n",
    "          cnts[ord(c) - ord('a')] += 1\n",
    "       res = 0\n",
    "       dfs(0, 0)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        # 每个单词的得分情况\n",
    "        ws = []\n",
    "        us = [Counter(word) for word in words]\n",
    "        total = Counter(letters)\n",
    "\n",
    "        for word in words:\n",
    "            cur = 0\n",
    "            for ch in word:\n",
    "                cur += score[ord(ch) - ord('a')]\n",
    "            ws.append(cur)\n",
    "        \n",
    "        def satisfied(cnt1, cnt2):\n",
    "            chs = [chr(i + 97) for i in range(26)]\n",
    "            for ch in chs:\n",
    "                if cnt1[ch] > cnt2[ch]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 枚举每个单词选不选\n",
    "        ans = 0\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = Counter()\n",
    "            curs = 0\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += us[i]\n",
    "                    curs += ws[i]\n",
    "            if satisfied(cnt, total):\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        cnt = [0] * 26\n",
    "        for c in letters: cnt[ord(c[0]) - ord('a')] += 1\n",
    "        res = 0\n",
    "        for s in range(1 << n):\n",
    "            cur = [0] * 26\n",
    "            for i in range(n):\n",
    "                if s & (1 << i) == 0: continue\n",
    "                for c in words[i]: cur[ord(c) - ord('a')] += 1\n",
    "            \n",
    "            flag = True\n",
    "            sc = 0\n",
    "            for i in range(26):\n",
    "                sc += cur[i] * score[i]\n",
    "                if cur[i] > cnt[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag: res = max(res, sc)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        self.words = words\n",
    "        self.words_cnt_list = [collections.Counter(word) for word in words]\n",
    "        self.letter_cnt_map = collections.Counter(letters)\n",
    "        self.score = score\n",
    "        self.score_max = 0\n",
    "        self.dfs(0, 0)\n",
    "        return self.score_max\n",
    "\n",
    "    def dfs(self, cur_score, idx):\n",
    "        if idx >= len(self.words):\n",
    "            self.score_max = max(self.score_max, cur_score)\n",
    "            return\n",
    "\n",
    "        can_spill = True\n",
    "        for k in self.words_cnt_list[idx]:\n",
    "            if self.words_cnt_list[idx][k] > self.letter_cnt_map[k]:\n",
    "                can_spill = False\n",
    "                break\n",
    "\n",
    "        self.dfs(cur_score, idx + 1)\n",
    "\n",
    "        if can_spill:\n",
    "            for k in self.words_cnt_list[idx]:\n",
    "                self.letter_cnt_map[k] -= self.words_cnt_list[idx][k]\n",
    "                cur_score += self.score[ord(k)-ord('a')] * self.words_cnt_list[idx][k]\n",
    "            self.dfs(cur_score, idx + 1)\n",
    "            for k in self.words_cnt_list[idx]:\n",
    "                self.letter_cnt_map[k] += self.words_cnt_list[idx][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        a, n = 0, len(words)\n",
    "        lc = Counter(letters)\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            wc = Counter(\"\".join([words[j] for j in range(n) if 1 << j & i]))\n",
    "            if all(wc[c] <= lc[c] for c in wc):\n",
    "                a = max(a, sum(v * score[ord(c)-ord('a')] for c, v in wc.items()))\n",
    "                \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        total = Counter(letters)\n",
    "        ws = []\n",
    "        for word in words:\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += score[ord(ch) - ord('a')]\n",
    "            ws.append(tmp)\n",
    "\n",
    "        def check(cnt, total):\n",
    "            for k in cnt.keys():\n",
    "                if cnt[k] > total[k]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        for mask in range(1, 2 ** n):\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            cnt = Counter()\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    curs += ws[i]\n",
    "                    cnt += Counter(words[i])\n",
    "                    if not check(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cnt = Counter(letters)\n",
    "        n = len(words)\n",
    "        def dfs(i,cnt):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            #不选\n",
    "            ans = dfs(i+1,cnt)\n",
    "            #选\n",
    "            cv = Counter(words[i])\n",
    "            if all(v<=cnt[k] for k,v in cv.items()):\n",
    "               ans = max(ans,sum(score[ord(k)-ord('a')]*v  for k,v in cv.items()) + dfs(i+1,cnt-cv))\n",
    "            return ans        \n",
    "        return dfs(0,cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        alph = [0]*26\n",
    "        for l in letters:\n",
    "            alph[ord(l)-97] += 1\n",
    "        @cache\n",
    "        def count(index):\n",
    "            maxi = 0\n",
    "            for i in range(len(words)):\n",
    "                if (index >> i) % 2 == 0:\n",
    "                    can = True\n",
    "                    value = 0\n",
    "                    for w in words[i]:\n",
    "                        alph[ord(w)-97] -= 1\n",
    "                        value += score[ord(w)-97]\n",
    "                        if alph[ord(w)-97] < 0: can = False\n",
    "                    if can: maxi = max(maxi, count(index|1<<i)+value)\n",
    "                    for w in words[i]:\n",
    "                        alph[ord(w)-97] += 1\n",
    "            return maxi\n",
    "\n",
    "        return count(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase, score))  # 字母对应的分数\n",
    "\n",
    "        def dfs(i: int, total: int) -> None:\n",
    "            if i < 0:  # base case\n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "\n",
    "            # 不选 words[i]\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 选 words[i]\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] == 0:  # 剩余字母不足\n",
    "                    for c in words[i][:j]:  # 撤销\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1  # 减少剩余字母\n",
    "                total += score[c]  # 累加得分\n",
    "\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 恢复现场\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cnt = [0] * 26\n",
    "        for _, x in enumerate(letters):\n",
    "            cnt[ord(x) - 97] += 1\n",
    "        ans = 0\n",
    "        def dfs(i: int, v: int) -> None:\n",
    "            nonlocal ans\n",
    "            if i >= len(words):\n",
    "                ans = max(ans, v)\n",
    "                return\n",
    "            # 不选第i个word\n",
    "            dfs(i + 1, v)\n",
    "            # 选第i个word\n",
    "            ok = True\n",
    "            for _, c in enumerate(words[i]):\n",
    "                if cnt[ord(c) - 97] == 0:\n",
    "                    ok = False\n",
    "                v += score[ord(c) - 97]\n",
    "                cnt[ord(c) - 97] -= 1\n",
    "            if ok:                  # 如果为False表示剩余单词数不足，无法选第i个word\n",
    "                dfs(i + 1, v)\n",
    "            # 恢复现场\n",
    "            for _, c in enumerate(words[i]):\n",
    "                cnt[ord(c) - 97] += 1\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        # 每个单词的得分情况\n",
    "        ws = []\n",
    "        us = [Counter(word) for word in words]\n",
    "        total = Counter(letters)\n",
    "\n",
    "        for word in words:\n",
    "            cur = 0\n",
    "            for ch in word:\n",
    "                cur += score[ord(ch) - ord('a')]\n",
    "            ws.append(cur)\n",
    "        \n",
    "        def satisfied(cnt1, cnt2):\n",
    "            chs = [chr(i + 97) for i in range(26)]\n",
    "            for ch in chs:\n",
    "                if cnt1[ch] > cnt2[ch]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 枚举每个单词选不选\n",
    "        ans = 0\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = Counter()\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += us[i]\n",
    "                    curs += ws[i]\n",
    "                    if not satisfied(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans=0\n",
    "        left=Counter(letters)\n",
    "        score=dict(zip(ascii_lowercase,score))\n",
    "\n",
    "        def dfs(i,total):\n",
    "            if i<0:\n",
    "                nonlocal ans\n",
    "                ans=max(ans,total)\n",
    "                return\n",
    "            dfs(i-1,total)\n",
    "\n",
    "            for j,c in enumerate(words[i]):\n",
    "                if left[c]==0:\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c]+=1\n",
    "                    return\n",
    "                left[c]-=1\n",
    "                total+=score[c]\n",
    "            dfs(i-1,total)\n",
    "\n",
    "            for c in words[i]:\n",
    "                left[c]+=1\n",
    "        \n",
    "        dfs(len(words)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        \n",
    "        n = len(words)\n",
    "        left = Counter(letters)\n",
    "        ws = []\n",
    "        for word in words:\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += score[ord(ch) - ord('a')]\n",
    "            ws.append(tmp)\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        def dfs(i, curs):\n",
    "            nonlocal left\n",
    "            \n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, curs)\n",
    "                return\n",
    "            \n",
    "            # 不管i位置的数字\n",
    "            dfs(i-1, curs)\n",
    "\n",
    "\n",
    "            # 可行的话考虑i位置的数字：\n",
    "            flag = True\n",
    "            cnt = Counter(words[i])\n",
    "            for k in cnt:\n",
    "                if cnt[k] > left[k]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                left -= cnt\n",
    "                curs += ws[i]\n",
    "                dfs(i-1, curs)\n",
    "                left += cnt\n",
    "        \n",
    "\n",
    "        dfs(n-1, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        cnt = Counter(letters)\n",
    "        d = dict(zip(ascii_lowercase,score))\n",
    "        def dfs(i,val):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,val)\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i-1,val)\n",
    "            # 选\n",
    "            for j,c in enumerate(words[i]):\n",
    "                if cnt[c] == 0:\n",
    "                    # 恢复前面的\n",
    "                    for c in words[i][:j]:\n",
    "                        cnt[c] += 1\n",
    "                    return \n",
    "                cnt[c] -= 1\n",
    "                val += d[c]\n",
    "            dfs(i-1,val)\n",
    "            # 恢复现场\n",
    "            for c in words[i]:\n",
    "                cnt[c] += 1\n",
    "        dfs(n-1,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        def lt1255(words,letters,scores):\n",
    "            d=defaultdict(int)\n",
    "            for ch in letters:d[ch]+=1\n",
    "            n=len(words)\n",
    "            word_score=defaultdict(int)\n",
    "            for word in words:\n",
    "                word_score[word]=sum([scores[ord(ch)-ord('a')] for ch in word])\n",
    "            def is_available(mask):\n",
    "                temp=[]\n",
    "                idx=n-1\n",
    "                while mask>0:\n",
    "                    if mask&1:temp.append(words[idx])\n",
    "                    mask>>=1\n",
    "                    idx-=1\n",
    "                d_=defaultdict(int)\n",
    "                for word in temp:\n",
    "                    for ch in word:\n",
    "                        d_[ch]+=1\n",
    "                        if d_[ch]>d[ch]:return False\n",
    "                return True\n",
    "            dp=[0]*(1<<n)\n",
    "            for i in range(1,1<<n):\n",
    "                if is_available(i):\n",
    "                    temp=i\n",
    "                    idx=n-1\n",
    "                    while temp:\n",
    "                        if temp&1:dp[i]+=word_score[words[idx]]\n",
    "                        idx-=1\n",
    "                        temp>>=1\n",
    "            return max(dp)\n",
    "        return lt1255(words,letters,score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        def dfs(i, l):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            s = 0\n",
    "            l2 = l\n",
    "            for c in words[i]:\n",
    "                if c not in l2:\n",
    "                    return dfs(i+1, l)\n",
    "                s += score[ord(c)-ord('a')]\n",
    "                l2 = l2.replace(c, '', 1)\n",
    "\n",
    "            return max(dfs(i+1, l), s + dfs(i+1, l2))\n",
    "        return dfs(0, \"\".join(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        self.ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(total, curPos, left):\n",
    "            if curPos == len(words):\n",
    "                self.ans = max(self.ans, total)\n",
    "                return\n",
    "            dfs(total, curPos+1, left)\n",
    "            if Counter(words[curPos]) <= left:\n",
    "                addtion = sum([score[n] for n in words[curPos]])\n",
    "                dfs(total + addtion, curPos+1, left - Counter(words[curPos]))\n",
    "        dfs(0, 0, left)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        c = Counter(letters)\n",
    "\n",
    "        m = len(words)\n",
    "        ans = 0\n",
    "        for i in range(1, 1<<m + 1):\n",
    "            cnt = Counter()\n",
    "            for j in range(m):\n",
    "                if i & (1<<j):\n",
    "                    cnt += Counter(words[j])\n",
    "            s = 0\n",
    "            flag = True\n",
    "            for key, value in cnt.items():\n",
    "                if value > c[key]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                s += score[ord(key) - ord('a')] * value\n",
    "            \n",
    "            if flag:\n",
    "                if s > ans:\n",
    "                    ans = s\n",
    "        return ans\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(i, total):\n",
    "            if i<0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "            dfs(i-1, total)\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] == 0:\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1\n",
    "                total += score[c]\n",
    "            dfs(i-1, total)\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        # 每个单词的得分情况\n",
    "        ws = []\n",
    "        us = [Counter(word) for word in words]\n",
    "        total = Counter(letters)\n",
    "\n",
    "        for word in words:\n",
    "            cur = 0\n",
    "            for ch in word:\n",
    "                cur += score[ord(ch) - ord('a')]\n",
    "            ws.append(cur)\n",
    "        \n",
    "        def satisfied(cnt1, cnt2):\n",
    "            for ch in cnt1.keys():\n",
    "                if cnt1[ch] > cnt2[ch]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 枚举每个单词选不选\n",
    "        ans = 0\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = Counter()\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += us[i]\n",
    "                    curs += ws[i]\n",
    "                    if not satisfied(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        # 题意你需要用letters中的字母去拼写单词，如果拼写的单词\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase,score))\n",
    "        def dfs(i,total):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,total)\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i-1,total)\n",
    "            # 选word[i]\n",
    "            for j,c in enumerate(words[i]):\n",
    "                if left[c] == 0:\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1\n",
    "                total += score[c]\n",
    "            dfs(i-1,total)\n",
    "            # 恢复现场\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "        dfs(len(words)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        c = Counter(letters)\n",
    "        ans = 0\n",
    "        n = len(words)\n",
    "        for i in range(1<<n + 1):\n",
    "            cnt = Counter()\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    cnt += Counter(words[j])\n",
    "            s = 0\n",
    "            flag = True\n",
    "            for key, value in cnt.items():\n",
    "                if value > c[key]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                s += value * score[ord(key) - ord('a')]\n",
    "            if flag: ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        self.ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(total, curPos, left):\n",
    "            if curPos == len(words):\n",
    "                self.ans = max(self.ans, total)\n",
    "                return\n",
    "            dfs(total, curPos+1, left)\n",
    "            if Counter(words[curPos]) <= left:\n",
    "                addtion = sum([score[n] for n in words[curPos]])\n",
    "                dfs(total + addtion, curPos+1, left - Counter(words[curPos]))\n",
    "        dfs(0, 0, left)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cnt = Counter(letters)\n",
    "        n = len(words)\n",
    "        def f(i: int, cnt: Counter) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            # 对于 words[i] 有选或不选两种可能\n",
    "            res = f(i + 1, cnt)\n",
    "            need = Counter(words[i])\n",
    "            if all(cnt[c] >= need[c] for c in words[i]):\n",
    "                res = max(res, f(i + 1, cnt - need) + sum(score[ord(c) - ord('a')] for c in words[i]))\n",
    "            return res\n",
    "        return f(0, cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))  # 字母对应的分数\n",
    "\n",
    "        def dfs(i: int, left: Counter) -> int:\n",
    "            if i < 0:  # base case\n",
    "                return 0\n",
    "\n",
    "            # 不选 words[i]\n",
    "            res = dfs(i - 1, left)\n",
    "\n",
    "            # 选 words[i]\n",
    "            cw = Counter(words[i])\n",
    "            if all(v <= left.get(k, 0) for k, v in cw.items()):  # 可以选\n",
    "                res = max(res, sum(score[c] for c in words[i]) + dfs(i - 1, left - cw))\n",
    "            return res\n",
    "\n",
    "        return dfs(len(words) - 1, Counter(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        lc = Counter(letters)\n",
    "        a = 0\n",
    "\n",
    "        def dfs(i, total):\n",
    "            if i >= n:\n",
    "                nonlocal a\n",
    "                a = max(a, total)\n",
    "                return\n",
    "\n",
    "\n",
    "            dfs(i+1, total)\n",
    "\n",
    "\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if lc[c] <= 0:\n",
    "                    for c in words[i][:j]:\n",
    "                        lc[c] += 1\n",
    "                    return\n",
    "                lc[c] -= 1\n",
    "                total += score[ord(c)-ord('a')]\n",
    "            dfs(i+1, total)\n",
    "            for c in words[i]:\n",
    "                lc[c] += 1\n",
    "\n",
    "            return\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cur = [0] * len(words)\n",
    "        letterCount = []\n",
    "        wordScore = [0] * len(words)\n",
    "        for i in range(len(words)):\n",
    "            letterCount.append([0] * 26)\n",
    "            for c in words[i]:\n",
    "                k = ord(c) - ord('a')\n",
    "                letterCount[i][k] += 1\n",
    "                wordScore[i] += score[k]\n",
    "\n",
    "        package = [0] * 26\n",
    "        for c in letters:\n",
    "            package[ord(c) - ord('a')] += 1\n",
    "\n",
    "        currentScore = 0\n",
    "        res = 0\n",
    "        currentLetters = [0] * 26\n",
    "        while cur[-1] < 2:\n",
    "            cur[0] += 1\n",
    "            if cur[0] == 1:\n",
    "                currentScore += wordScore[0]\n",
    "                self.A(currentLetters, letterCount[0])\n",
    "            else:\n",
    "                i = 0\n",
    "                while cur[i] == 2:\n",
    "                    cur[i] = 0\n",
    "                    currentScore -= wordScore[i]\n",
    "                    self.D(currentLetters, letterCount[i])\n",
    "                    i += 1\n",
    "                    if i == len(cur):\n",
    "                        break \n",
    "                    cur[i] += 1\n",
    "                if i != len(cur):\n",
    "                    currentScore += wordScore[i]\n",
    "                    self.A(currentLetters, letterCount[i])\n",
    "                else:\n",
    "                    break\n",
    "            if self.C(currentLetters, package):\n",
    "                res = max(res, currentScore)\n",
    "        return res\n",
    "    \n",
    "    def C(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            if x[i] > y[i]:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def A(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            x[i] += y[i]\n",
    "    \n",
    "    def D(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            x[i] -= y[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        def lt1255(words,letters,scores):\n",
    "            d=defaultdict(int)\n",
    "            for ch in letters:d[ch]+=1\n",
    "            n=len(words)\n",
    "            word_score=defaultdict(int)\n",
    "            for word in words:\n",
    "                word_score[word]=sum([scores[ord(ch)-ord('a')] for ch in word])\n",
    "            def is_available(mask):\n",
    "                temp=[]\n",
    "                idx=n-1\n",
    "                while mask>0:\n",
    "                    if mask&1:temp.append(words[idx])\n",
    "                    mask>>=1\n",
    "                    idx-=1\n",
    "                d_=defaultdict(int)\n",
    "                for word in temp:\n",
    "                    for ch in word:\n",
    "                        d_[ch]+=1\n",
    "                        if d_[ch]>d[ch]:return False\n",
    "                return True\n",
    "            dp=[0]*(1<<n)\n",
    "            for i in range(1,1<<n):\n",
    "                if dp[i]==-1:continue\n",
    "                if is_available(i):\n",
    "                    temp=i\n",
    "                    idx=n-1\n",
    "                    while temp:\n",
    "                        if temp&1:dp[i]+=word_score[words[idx]]\n",
    "                        idx-=1\n",
    "                        temp>>=1\n",
    "                else:\n",
    "                    dp[i]=-1\n",
    "                    for j in range(i+1,1<<n):\n",
    "                        if i&j==i:dp[j]=-1\n",
    "            return max(max(dp),0)\n",
    "        return lt1255(words,letters,score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:#tuple或字典dp\n",
    "        letters=Counter(letters)\n",
    "        k=tuple([letters[chr(ord('a')+i)] for i in range(26)])\n",
    "        dp=Counter()\n",
    "        dp[deepcopy(k)]=0\n",
    "        for w in words:\n",
    "            ct=Counter(w)\n",
    "            tp=dp.copy()#deepcopy(dp)\n",
    "            for j in tp:\n",
    "                l=list(j)\n",
    "                canJoin=True\n",
    "                for i in ct:\n",
    "                    if ct[i]>l[ord(i)-ord('a')]:\n",
    "                        canJoin=False\n",
    "                        break\n",
    "                    l[ord(i)-ord('a')]-=ct[i]\n",
    "                if not canJoin:continue\n",
    "                l=tuple(l)\n",
    "                sm=sum(score[ord(i)-ord('a')]*ct[i] for i in ct)\n",
    "                if l not in dp:dp[l]=dp[j]+sm\n",
    "                else:dp[l]=max(dp[j]+sm,dp[l])\n",
    "            # dp[letters]=0\n",
    "        # print(k)\n",
    "        # print(dp.most_common(1)[0])\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        \n",
    "        # 如果比letters中的要多，则得分为0\n",
    "        # 如果比letters中的要少，则统计份数，和max值进行比较\n",
    "        # 难点在于找出所有单词的组合\n",
    "\n",
    "        # 统计letters的字母数\n",
    "        dl = {}\n",
    "        r = 0\n",
    "        for l in letters:\n",
    "            if l not in dl:\n",
    "                dl[l] = 1\n",
    "            else:\n",
    "                dl[l] += 1\n",
    "\n",
    "        for i in range(1, len(words)+1):\n",
    "            # 找出所有单词的组合\n",
    "            combinations = itertools.combinations(words, i)\n",
    "            # 将每个单词组合的字母数group统计\n",
    "            for c in combinations:\n",
    "                d = {}\n",
    "                for w in c:\n",
    "                    for ww in w:\n",
    "                        if ww not in d:\n",
    "                            d[ww] = 1\n",
    "                        else:\n",
    "                            d[ww] += 1\n",
    "                # print(c, d)\n",
    "                hege = 1\n",
    "                for k in d:\n",
    "                    if k in dl and d[k] <= dl[k]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        hege = 0\n",
    "                        break\n",
    "                if hege:\n",
    "                    # 计算得分\n",
    "                    s = 0\n",
    "                    for k in d:\n",
    "                        s += (score[ord(k)-ord('a')] *d[k])\n",
    "                    if s > r:\n",
    "                        r = s\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        \n",
    "        def f(i: int, cnt: Counter) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            # 当前单词选或不选\n",
    "            res = f(i - 1, cnt) # 不选当前单词\n",
    "            ct = Counter(words[i])\n",
    "            if all(v <= cnt.get(k, 0) for k, v in ct.items()):\n",
    "                res = max(res, sum(score[ord(c) - ord('a')] for c in words[i]) + f(i - 1, cnt - ct))\n",
    "            return res\n",
    "        \n",
    "        return f(n - 1, Counter(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        total = Counter(letters)\n",
    "        ws = []\n",
    "        for word in words:\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += score[ord(ch) - ord('a')]\n",
    "            ws.append(tmp)\n",
    "\n",
    "        def check(cnt, total):\n",
    "            for k in cnt.keys():\n",
    "                if cnt[k] > total[k]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        for mask in range(1, 2 ** n):\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            cnt = Counter()\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    curs += ws[i]\n",
    "                    cnt += Counter(words[i])\n",
    "                    if not check(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                print(bin(mask), cnt, total, ans, curs)\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        words_len = len(words)\n",
    "        words_cout= [[0]*26 for i in range(words_len)]\n",
    "        # words_cout= []\n",
    "        for i in range(words_len):\n",
    "            for w in words[i]:\n",
    "                words_cout[i][ord(w)-97]+=1\n",
    "        a_count = [0]*26\n",
    "        for a in letters:\n",
    "            a_count[ord(a)-97]+=1\n",
    "        def check(index):\n",
    "            word = words[index]\n",
    "            for w in word:\n",
    "                w_ord = ord(w)-97\n",
    "                if a_count[w_ord] < words_cout[index][w_ord]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # def traceback(i):\n",
    "        #     if i>=words_len:\n",
    "        #         return 0\n",
    "        #     if not check(i):\n",
    "        #         return traceback(i+1)\n",
    "        #     t = 0 \n",
    "        #     soc = 0\n",
    "        #     for w in words[i]:\n",
    "        #         w_ord = ord(w)-97\n",
    "        #         a_count[w_ord]-=1\n",
    "        #         print(words[i], w_ord)\n",
    "        #         soc+= score[w_ord]\n",
    "        #     for j in range(i+1, words_len):\n",
    "        #         t_s = traceback(j)\n",
    "        #         soc += t_s\n",
    "        #         t = max(t, soc)\n",
    "        #         soc-= t_s\n",
    "        #     for w in words[i]:\n",
    "        #         a_count[w_ord]+=1\n",
    "        #     return max(t, soc)\n",
    "                    \n",
    "        def dfs(i):\n",
    "            if i <0:\n",
    "                return 0\n",
    "            t = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if check(j):\n",
    "                    not_selct= dfs(j-1)\n",
    "                    # print(\"not_selct\",not_selct)\n",
    "                    soc = 0\n",
    "                    for w in words[j]:\n",
    "                        w_ord = ord(w)-97\n",
    "                        a_count[w_ord]-=1\n",
    "                        # print(words[j], w_ord)\n",
    "                        soc+= score[w_ord]\n",
    "                    # print(\"soc\",soc)    \n",
    "                    select_ = soc+ dfs(j-1)\n",
    "\n",
    "                    # print(\"select_\",select_)\n",
    "                    t = max(t, not_selct,select_)\n",
    "                    for w in words[j]:\n",
    "                        w_ord = ord(w)-97\n",
    "                        a_count[w_ord]+=1\n",
    "            # print(t)\n",
    "            return t\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in range(words_len):\n",
    "        #     ans = max(ans, dfs(i))\n",
    "        return dfs(words_len-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase, score))  # 字母对应的分数\n",
    "\n",
    "        def dfs(i: int, total: int) -> None:\n",
    "            if i < 0: \n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 选 words[i]\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] == 0: \n",
    "                    for c in words[i][:j]:  \n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1  \n",
    "                total += score[c]\n",
    "            dfs(i - 1, total)\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "\n",
    "        def dfs(i, total):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return \n",
    "            \n",
    "            # 不选words[i]\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 选words[i]\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] > 0:\n",
    "                    left[c] -= 1\n",
    "                    total += score[c]\n",
    "                else:\n",
    "                    # 如果这个单词加到一半加不下去了，没有letter可选了，进行回溯，把加过去的去掉\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i, l):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            s = 0\n",
    "            l2 = l\n",
    "            for c in words[i]:\n",
    "                if c not in l2:\n",
    "                    return dfs(i+1, l)\n",
    "                s += score[ord(c)-ord('a')]\n",
    "                l2 = l2.replace(c, '', 1)\n",
    "\n",
    "            return max(dfs(i+1, l), s + dfs(i+1, l2))\n",
    "        return dfs(0, \"\".join(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ws = [Counter(i) for i in words]\n",
    "        letters = Counter(letters)\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            \n",
    "            d = {}\n",
    "            \n",
    "            for i in range(n):\n",
    "                if state >> i & 1:\n",
    "                    for k, v in ws[i].items():\n",
    "                        d[k] = d.get(k, 0) + v\n",
    "                        if d[k] > letters[k]:\n",
    "                            return 0\n",
    "            ans = sum([score[ord(ch) - 97] * d[ch] for ch in d])\n",
    "            # 处理未选的情况\n",
    "            for i in range(n):\n",
    "                if state >> i & 1 == 0:\n",
    "                    ans = max(ans, dfs(state | 1 << i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ws = [Counter(i) for i in words]\n",
    "        letters = Counter(letters)\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            d = {}\n",
    "            for i in range(n):\n",
    "                if state >> i & 1:\n",
    "                    for k, v in ws[i].items():\n",
    "                        d[k] = d.get(k, 0) + v\n",
    "                        if d[k] > letters[k]:\n",
    "                            return 0\n",
    "            ans = sum([score[ord(ch) - 97] * d[ch] for ch in d])\n",
    "            # 处理未选的情况\n",
    "            for i in range(n):\n",
    "                if state >> i & 1 == 0:\n",
    "                    ans = max(ans, dfs(state | 1 << i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        # 统计单词需要的字母-个数\n",
    "        words_cnt = [Counter(word) for word in words]\n",
    "        # 统计字符集的字母情况\n",
    "        letters_cnt = Counter(letters)\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            # 统计当前状态下字符占用情况\n",
    "            d = dict()\n",
    "            for i in range(n):\n",
    "                # 当前状态已选第i个word\n",
    "                if state >> i & 1 == 1:\n",
    "                    for ch, v in words_cnt[i].items():\n",
    "                        d[ch] = d.get(ch, 0) + v\n",
    "                        # 字符集不支持，这个state不合理\n",
    "                        if d[ch] > letters_cnt.get(ch, 0):\n",
    "                            return 0\n",
    "            ans = sum([score[ord(ch)-ord('a')]* d[ch] for ch in d])\n",
    "            \n",
    "            for i in range(n):\n",
    "                if state >> i & 1 == 0:\n",
    "                    ans = max(ans, dfs(state | 1<<i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        idxs2 = [i for i in range(n)]\n",
    "        idxs2.sort(key = lambda i: nums2[i], reverse = True)\n",
    "\n",
    "        res = 0\n",
    "        minHeap = []\n",
    "        sum1 = 0\n",
    "        for idx in idxs2:\n",
    "            x = nums1[idx]\n",
    "            y = nums2[idx]\n",
    "            while len(minHeap) > k - 1:\n",
    "                sum1 -= heapq.heappop(minHeap)\n",
    "            heapq.heappush(minHeap, x)\n",
    "            sum1 += x\n",
    "\n",
    "            if len(minHeap) == k:\n",
    "                cur = sum1 * y\n",
    "                res = max(res, cur)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        idxs2 = [i for i in range(n)]\n",
    "        idxs2.sort(key = lambda i: nums2[i], reverse = True)\n",
    "\n",
    "        res = 0\n",
    "        minHeap = []\n",
    "        sum1 = 0\n",
    "        for idx in idxs2:\n",
    "            x = nums1[idx]\n",
    "            y = nums2[idx]\n",
    "            while len(minHeap) > k - 1:\n",
    "                sum1 -= heapq.heappop(minHeap)\n",
    "            heapq.heappush(minHeap, x)\n",
    "            sum1 += x\n",
    "\n",
    "            if len(minHeap) == k:\n",
    "                cur = sum1 * y\n",
    "                res = max(res, cur)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums2)\n",
    "        idx = [i for i in range(n)]\n",
    "        idx.sort(key=lambda i: nums2[i], reverse=True)\n",
    "\n",
    "        sumh = [nums1[i] for i in idx[:k]]\n",
    "        heapq.heapify(sumh)\n",
    "        s = sum(sumh)\n",
    "        res = s * nums2[idx[k-1]]\n",
    "        # print(res, sumh, s, nums2[idx[k-1]])\n",
    "        for i in idx[k:]:\n",
    "            if nums1[i] > sumh[0]:\n",
    "                num = heapq.heappop(sumh)\n",
    "                s = s - num + nums1[i]\n",
    "                res = max(res, s * nums2[i])\n",
    "                heapq.heappush(sumh, nums1[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        idxs2 = [i for i in range(n)]\n",
    "        idxs2.sort(key = lambda i: nums2[i], reverse = True)\n",
    "\n",
    "        res = 0\n",
    "        minHeap = []\n",
    "        sum1 = 0\n",
    "        for idx in idxs2:\n",
    "            x = nums1[idx]\n",
    "            y = nums2[idx]\n",
    "            while len(minHeap) > k - 1:\n",
    "                sum1 -= heapq.heappop(minHeap)\n",
    "            heapq.heappush(minHeap, x)\n",
    "            sum1 += x\n",
    "\n",
    "            if len(minHeap) == k:\n",
    "                cur = sum1 * y\n",
    "                res = max(res, cur)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, a: List[int], b: List[int], k: int) -> int:\n",
    "        s = sorted(range(len(a)), key = lambda x:b[x])\n",
    "        h = []\n",
    "       \n",
    "        for j in range(-1, -k - 1, -1):\n",
    "            i = s[j]\n",
    "            h.append(a[i])\n",
    "        ans = sum(h)*b[i]\n",
    "        pre = sum(h)\n",
    "        print(pre, ans)\n",
    "        heapq.heapify(h)\n",
    "        for j in range(0, len(a)-k)[::-1]:\n",
    "            i = s[j]\n",
    "            heapq.heappush(h, a[i])\n",
    "            tmp = heapq.heappop(h)\n",
    "            pre -= tmp \n",
    "            pre += a[i]\n",
    "            ans = max(ans, pre*b[i])  \n",
    "        return ans \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nl = [[xx, yy] for xx,yy in zip(nums1,nums2)]\n",
    "        nls = sorted(nl,key=lambda x:x[1],reverse=True)\n",
    "        h = [x for x,_ in nls[:k]]\n",
    "        s = sum(h)\n",
    "        heapify(h)\n",
    "        ans = s * nls[k-1][1]\n",
    "        for x,y in nls[k:]:\n",
    "            if x > h[0]:\n",
    "                s +=x- heapreplace(h, x)\n",
    "                ans = max(ans, s*y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = []\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append([nums1[i],nums2[i]])\n",
    "        nums = sorted(nums,key=lambda x:x[1],reverse=True)\n",
    "        pq = []\n",
    "        mmin,ans,x,y = int(1e9),-1,0,0\n",
    "        for i in range(k):\n",
    "            pq.append(nums[i][0])\n",
    "            x += nums[i][0]\n",
    "            y = nums[i][1]\n",
    "            mmin = min(mmin,nums[i][0])\n",
    "        ans = max(ans,x*y)\n",
    "        heapq.heapify(pq)\n",
    "        for i in range(len(nums)-k):\n",
    "            j = i+k\n",
    "            qq = nums[j][0]\n",
    "            y = nums[j][1]\n",
    "            if qq > mmin:\n",
    "                heapq.heapreplace(pq,qq)\n",
    "                x += qq - mmin\n",
    "                mmin = heapq.heappop(pq)\n",
    "                heapq.heappush(pq,mmin)\n",
    "            ans = max(ans,x*y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/kth-largest-element-in-a-stream/\n",
    "    # https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = sorted(list(zip(nums2, nums1))) # 按nums2排序\n",
    "        tot = res = 0\n",
    "        heap = []\n",
    "        # 选择 nums[i][0] 作为最小值  nums[i][1]作为和之一, 之后在nums[i+1][1] ... nums[n-1][1] 选择前k-1个最大值即可\n",
    "        # 可以使用一个最大容量为k-1 的小根堆, 同时维护一个变量,代表堆中元素之和(最后这个变量就是前k-1个最大值之和)\n",
    "        # 堆容量小于k-1:直接入堆,同时修改堆中元素之和\n",
    "        for i in range(n - k + 1, n):\n",
    "            heappush(heap, nums[i][1]) \n",
    "            tot += nums[i][1]\n",
    "\n",
    "        print(nums)\n",
    "        print(tot)\n",
    "        # 此时堆的容量为k-1\n",
    "        # 枚举可以选择的min(nums2[i])\n",
    "        for i in range(n - k, -1, -1): # 注意这个遍历顺序,如果正向遍历,每次处理的区间变小,就无法利用上一次循环堆中保存的结果\n",
    "            # 堆容量等于k-1:\n",
    "            # 1) 当add的元素大于堆顶,出堆顶(因为堆顶是最小的,不可作为结果,同时修改堆中元素之和)\n",
    "            # 2) 当add的元素小于等于堆顶,什么都不做\n",
    "            res = max(res, (nums[i][1] + tot) * nums[i][0])\n",
    "            if heap and nums[i][1] > heap[0]: # 如果输入k=1 ,那么堆会一直为空,因此需要判断\n",
    "                tot = tot - heapreplace(heap, nums[i][1]) + nums[i][1] # heapreplace 返回的是之前的堆顶元素\n",
    "                # -= 会把后面的也减掉,因为不可-=\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        z = [0] *n\n",
    "        for i in range(n):\n",
    "            z[i] = (nums1[i],nums2[i])\n",
    "        z.sort(key = lambda x:-x[1])\n",
    "        h = [g[0] for g in z[:k]]\n",
    "        heapq.heapify(h)\n",
    "        t = sum(h)\n",
    "        ans = t*z[k-1][1]\n",
    "        for x,y in z[k:]:\n",
    "            if x > h[0]:\n",
    "                t += x - heapq.heapreplace(h,x)\n",
    "                ans = max(ans,t*y)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: -p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k - 1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - h[0]\n",
    "                heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        z = [0] *n\n",
    "        for i in range(n):\n",
    "            z[i] = (nums1[i],nums2[i])\n",
    "        z.sort(key = lambda x:-x[1])\n",
    "        h = [g[0] for g in z[:k]]\n",
    "        heapq.heapify(h)\n",
    "        t = sum(h)\n",
    "        ans = t*z[k-1][1]\n",
    "        for x,y in z[k:]:\n",
    "            if x > h[0]:\n",
    "                t += x - heapq.heapreplace(h,x)\n",
    "                ans = max(ans,t*y)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = zip(nums1, nums2)\n",
    "        a = sorted(a, key=lambda x:-x[1])\n",
    "\n",
    "        b = a[:k]\n",
    "\n",
    "        nums1_sub = [ele[0] for ele in b]\n",
    "        heapify(nums1_sub)\n",
    "\n",
    "        s = sum(nums1_sub)\n",
    "        ans = b[-1][1] * s\n",
    "        for ele in a[k:]:\n",
    "            if nums1_sub[0] < ele[0]:\n",
    "                s = s + ele[0] - nums1_sub[0]\n",
    "                heapreplace(nums1_sub, ele[0])\n",
    "                ans = max(ans, s * ele[1])\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        # 组合nums1和nums2，再根据nums2降序排列，枚举k\n",
    "        tmp = sorted(zip(nums1, nums2), key=lambda x: -x[1])\n",
    "        heap = [x for x, _ in tmp[:k]]\n",
    "        heapq.heapify(heap)\n",
    "        s = sum(heap)\n",
    "        ans = s * tmp[k - 1][1]\n",
    "        for x, y in tmp[k:]:\n",
    "            if x <= heap[0]:\n",
    "                continue\n",
    "            s += (x - heapq.heapreplace(heap, x))\n",
    "            ans = max(ans, s * y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        # 子序列不是动态规划就是排序+贪心\n",
    "        # 然后答案一定在以当前的nums[i]为最小值时，左边可以取的下标里nums1[i]的最大和\n",
    "        # 因为求在线的topk大，所以用堆，将遍历的每个x加入最大堆，然后取前k的和\n",
    "        a=sorted(zip(nums1,nums2),key=lambda x:-x[1])\n",
    "        h=[x for x,_ in a[:k]]\n",
    "        heapify(h)\n",
    "        s=sum(h)\n",
    "        res=s*a[k-1][1]\n",
    "        for x,y in a[k:]:\n",
    "            if x>h[0]:\n",
    "                s+=x-heapreplace(h,x)\n",
    "                res=max(res,s*y)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        #思路：遍历数组，假设当前最小索引为i的前提下，构建1个最大的乘积和\n",
    "        from sortedcontainers import SortedList\n",
    "        nums = []\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append([nums2[i], nums1[i]])\n",
    "        nums = sorted(nums, key=lambda x:x[0])\n",
    "        #print(nums)\n",
    "        sorted_list = SortedList([])\n",
    "        max_sub_sum = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if len(sorted_list) < k - 1:\n",
    "                sorted_list.add(nums[i][1])\n",
    "                max_sub_sum += nums[i][1]\n",
    "            else:\n",
    "                right = nums[i][0]\n",
    "                left = nums[i][1] + max_sub_sum\n",
    "                res = right * left\n",
    "                if res > ans:\n",
    "                    ans = res\n",
    "                #若当前的值大于排序数组中的最小值:\n",
    "                if k > 1 and nums[i][1] > sorted_list[0]:\n",
    "                    max_sub_sum += nums[i][1] - sorted_list[0]\n",
    "                    del sorted_list[0]\n",
    "                    sorted_list.add(nums[i][1])\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums2)\n",
    "        nums2_indexs = sorted(range(n),key = lambda i: -nums2[i])\n",
    "        heap = []\n",
    "        sum = 0\n",
    "        for i in nums2_indexs:\n",
    "            heappush(heap, nums1[i])\n",
    "            sum += nums1[i]\n",
    "            if len(heap) > k:\n",
    "                sum -= heappop(heap) \n",
    "            if len(heap) == k:\n",
    "                ans = max(ans, nums2[i] * sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pq = []\n",
    "        res = 0\n",
    "        curSum = 0\n",
    "        for min_, add in sorted(zip(nums2, nums1), reverse=True):\n",
    "            heappush(pq, add)\n",
    "            curSum += add\n",
    "            if len(pq) > k:\n",
    "                curSum -= heappop(pq)\n",
    "            if len(pq) == k:\n",
    "                res = max(res, curSum * min_)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        topk = SortedList(sorted(nums1)[-k:])\n",
    "        total = SortedList(nums1)\n",
    "        s = sum(topk)\n",
    "        index = [i for i in range(len(nums2))]\n",
    "        index.sort(key=lambda x:nums2[x])\n",
    "        res = 0\n",
    "        for i in index[:-k]:\n",
    "            res = max(res,s*nums2[i])\n",
    "            total.remove(nums1[i])\n",
    "            try:\n",
    "                topk.remove(nums1[i])\n",
    "                s-=nums1[i]\n",
    "                topk.add(total[-k])\n",
    "                s+=total[-k]\n",
    "            except:\n",
    "                pass\n",
    "        res = max(res, s * nums2[index[-k]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        res = list(zip(nums1, nums2))\n",
    "        res.sort(key=lambda x: -x[1])\n",
    "        tmp = []\n",
    "        ans = total = 0\n",
    "        for num1, num2 in res:\n",
    "            heappush(tmp, num1)\n",
    "            total += num1\n",
    "            if len(tmp) > k: \n",
    "                total -= heappop(tmp)\n",
    "            # 6302. 最大子序列的分数\n",
    "            if len(tmp) == k: \n",
    "                ans = max(ans, total * num2)\n",
    "            # 1383 最大的团队表现值\n",
    "            # if len(tmp) <= k: \n",
    "            #     ans = max(ans, total * num2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums2)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: -nums2[it])\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for i in ind:\n",
    "            heapq.heappush(stack, nums1[i])\n",
    "            pre += nums1[i]\n",
    "            while len(stack) > k:\n",
    "                pre -= heapq.heappop(stack)\n",
    "            if len(stack) == k:\n",
    "                ans = ans if ans > nums2[i]*pre else nums2[i]*pre\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        init_ns = sorted(zip(nums1, nums2), reverse=True, key=lambda t: t[1])\n",
    "        # init_ks = init_ns[:k]\n",
    "        # cand_ks = init_ns[k:]\n",
    "\n",
    "        h = []\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            heappush(h, init_ns[i][0])\n",
    "            s += init_ns[i][0]\n",
    "        # p = init_ns[k - 1]\n",
    "        ans = s * init_ns[k - 1][1]\n",
    "        for i in range(k, n):\n",
    "            if init_ns[i][0] > h[0]:\n",
    "                s = s + init_ns[i][0] - h[0]\n",
    "                heappop(h)\n",
    "                heappush(h, init_ns[i][0])\n",
    "            ans = max(ans, s * init_ns[i][1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        nums = [(nums2[i], nums1[i]) for i in range(n)]\n",
    "\n",
    "        nums.sort(reverse = True)\n",
    "        \n",
    "        S = 0\n",
    "        q = []\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            S += nums[i][1]\n",
    "            heapq.heappush(q, nums[i][1])\n",
    "        res = max(res, S * nums[k-1][0])\n",
    "        for i in range(k, n):\n",
    "            x = heapq.heappop(q)\n",
    "            t = nums[i][1]\n",
    "            if t > x:\n",
    "                heapq.heappush(q, t)\n",
    "                S += t - x\n",
    "            else:\n",
    "                heapq.heappush(q, x)\n",
    "            res = max(res, S * nums[i][0])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        z = list(zip(nums2, nums1))\n",
    "        z.sort()\n",
    "\n",
    "        res = 0\n",
    "        h = []\n",
    "        min2 = 1000000\n",
    "        tot = 0\n",
    "        for b,a in z[::-1]:\n",
    "            min2 = min(min2, b)\n",
    "            tot += a\n",
    "            heapq.heappush(h, a)\n",
    "            while len(h) > k:\n",
    "                tot -= heapq.heappop(h)\n",
    "            if len(h) == k:\n",
    "                res = max(res, tot * min2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = list(zip(nums1, nums2))\n",
    "        nums.sort(key=lambda x:-x[1])\n",
    "        hp = [x for x, _ in nums[:k]]\n",
    "        heapify(hp)\n",
    "        s = sum(hp)\n",
    "        ans = sum(hp) * nums[k - 1][1]\n",
    "        for x, y in nums[k:]:\n",
    "            if x > hp[0]:\n",
    "                s -= hp[0]\n",
    "                heapreplace(hp, x)\n",
    "                s += x\n",
    "                ans = max(ans, s * y)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        arr = [[a, b] for a, b in zip(nums1, nums2)]\n",
    "        arr.sort(key=lambda x: -x[1])\n",
    "        q = [v[0] for v in arr[:k]]\n",
    "        heapq.heapify(q)\n",
    "        s = sum(q)\n",
    "        ans = s * arr[k - 1][1]\n",
    "        for i in range(k, len(nums1)):\n",
    "            v = arr[i][0]\n",
    "            if q and v > q[0]:\n",
    "                heapq.heappush(q, v)\n",
    "                s -= heapq.heappop(q)\n",
    "                s += v\n",
    "                ans = max(ans, s * arr[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pq1 = []\n",
    "        pq2 = []\n",
    "        cur = 0\n",
    "        for u, v in zip(nums1, nums2):\n",
    "            pq1.append((-u, v))\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        heapq.heapify(pq1)\n",
    "        for curMin in sorted(list(set(nums2))):\n",
    "            while pq2 and pq2[0][0] < curMin:\n",
    "                cur -= pq2[0][1]\n",
    "                heapq.heappop(pq2)\n",
    "            while pq1 and len(pq2) < k:\n",
    "                if pq1[0][1] < curMin:\n",
    "                    heapq.heappop(pq1)\n",
    "                    continue\n",
    "                u, v = heapq.heappop(pq1)\n",
    "                u = -u\n",
    "                cur += u\n",
    "                heapq.heappush(pq2, (v, u))\n",
    "            if len(pq2) < k:\n",
    "                break\n",
    "            else:\n",
    "                ans = max(ans, curMin * cur)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n=len(nums1)\n",
    "        nums=[(nums1[i],nums2[i]) for i in range(n)]\n",
    "        nums.sort(key=lambda x:-x[1])\n",
    "        q=SortedList()\n",
    "        tmps,ans=0,0\n",
    "        for i in range(n):\n",
    "            q.add(nums[i][0])\n",
    "            tmps+=nums[i][0]\n",
    "            if len(q)>k:\n",
    "                tmps-=q.pop(0)\n",
    "            if len(q)==k:\n",
    "                ans=max(ans,tmps*nums[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = list(zip(nums2,nums1))\n",
    "        nums.sort(reverse=True)\n",
    "        q = PriorityQueue()\n",
    "        res = sums = 0\n",
    "        for n1,n2 in nums:\n",
    "            q.put(n2)\n",
    "            sums+=n2\n",
    "            if(q.qsize()>k):\n",
    "                sums-=q.get()\n",
    "            if(q.qsize()==k):\n",
    "                res=max(res,sums*n1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList as SL\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        arr = sorted(zip(nums1, nums2), key=lambda x: -x[1])\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        times = 0\n",
    "        sl = SL()\n",
    "        for a, b in arr:\n",
    "            sl.add(a)\n",
    "            total += a\n",
    "            if len(sl) > k:\n",
    "                total -= sl.pop(0)\n",
    "            if len(sl) == k:\n",
    "                ans = max(ans, total * b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        idx = sorted(list(range(n)),key=lambda x:-nums2[x])\n",
    "        nums1 = [nums1[i] for i in idx]\n",
    "        nums2 = [nums2[i] for i in idx]\n",
    "        q = []\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            heappush(q, nums1[i])\n",
    "            s += nums1[i]\n",
    "            if len(q) > k:\n",
    "                s -= heappop(q)\n",
    "            if len(q) == k:\n",
    "                ans = max(ans, s*nums2[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: -nums2[it])\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        pre = 0\n",
    "        for i in ind:\n",
    "            heapq.heappush(stack, nums1[i])\n",
    "            pre += nums1[i]\n",
    "            if len(stack) > k:\n",
    "                pre -= heapq.heappop(stack)\n",
    "            if len(stack) == k:\n",
    "                if pre*nums2[i] > ans:\n",
    "                    ans = pre*nums2[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Min Heap\n",
    "    time: O(nlogn) for sorted(), O(nlogk) for heappush(),\n",
    "        O((n-k)*logk) for heappop(), totally, O(nlogn)\n",
    "    space: O(n)\n",
    "    \"\"\"\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pairs = [(n1, n2) for n1, n2 in zip(nums1, nums2)]\n",
    "        pairs = sorted(pairs, key=lambda x: x[1], reverse=True)\n",
    "\n",
    "        min_heap = []\n",
    "        sum_n1 = 0\n",
    "        res = 0\n",
    "\n",
    "        for n1, n2 in pairs:\n",
    "            heapq.heappush(min_heap, n1)\n",
    "            sum_n1 += n1\n",
    "\n",
    "            if len(min_heap) > k:\n",
    "                sum_n1 -= heapq.heappop(min_heap)\n",
    "            if len(min_heap) == k:\n",
    "                res = max(res, sum_n1*n2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = sorted(zip(nums2,nums1),reverse=True)\n",
    "        #print(nums)\n",
    "        heap = []\n",
    "        #i = 0\n",
    "        #j = 1\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i != 0:     \n",
    "                heapq.heappush(heap,nums[i-1][1])\n",
    "                s += nums[i-1][1]\n",
    "            if i >= k:\n",
    "                s -= heap[0]\n",
    "                heapq.heappop(heap)\n",
    "            #print(i,s,(s+nums[i][1])*nums[i][0])\n",
    "            if i >= k-1:\n",
    "                ans = max(ans, (s+nums[i][1])*nums[i][0])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = list(zip(nums2, nums1))\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        arr = []\n",
    "        heapq.heapify(arr)\n",
    "\n",
    "        n = len(nums1)\n",
    "        csum = 0 # 最大的k个数。\n",
    "        ans = float(\"-inf\")\n",
    "        for i in range(n):\n",
    "            if i < k:\n",
    "                heapq.heappush(arr, nums[i][1])\n",
    "                csum += nums[i][1]\n",
    "                if i == k-1:\n",
    "                    ans = csum*nums[i][0]\n",
    "            else:\n",
    "                t = csum-arr[0]+nums[i][1]\n",
    "                ans = max(ans, t*nums[i][0])\n",
    "                heapq.heappush(arr, nums[i][1])\n",
    "                csum += nums[i][1]\n",
    "                csum -= heapq.heappop(arr)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        converge = []\n",
    "        for i in range(n):\n",
    "            converge.append((nums2[i],nums1[i]))\n",
    "        converge = sorted(converge, reverse = True)\n",
    "        res = 0\n",
    "        sumI = 0\n",
    "        minD = inf\n",
    "        for i in range(k):\n",
    "            sumI += converge[i][1]\n",
    "            minD = minD if minD < converge[i][0] else converge[i][0]\n",
    "        res = sumI*minD\n",
    "        selected = [x[1] for x in converge[:k]]\n",
    "        heapify(selected)\n",
    "        # 遍历后k个值\n",
    "        for i in range(k,n):\n",
    "            sumI = sumI - selected[0] + converge[i][1] \n",
    "            minD = converge[i][0]\n",
    "            heapreplace(selected, converge[i][1])\n",
    "            if sumI*minD > res:\n",
    "                res = sumI*minD\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = [(n2, n1) for n2, n1 in zip(nums2, nums1)]\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        max_k = []\n",
    "        sum_k = 0\n",
    "        for i, (n2, n1) in enumerate(nums):\n",
    "            if i < k-1:\n",
    "                heappush(max_k, n1)\n",
    "                sum_k += n1 \n",
    "            else:\n",
    "                ans = max(ans, (sum_k + n1) * n2)\n",
    "                heappush(max_k, n1)\n",
    "                sum_k -= heappop(max_k)\n",
    "                sum_k += n1 \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        cap = [(i,j) for i,j in zip(nums1,nums2)]\n",
    "        cap.sort(key = lambda x:x[1])\n",
    "        # print(cap)\n",
    "        heap = []\n",
    "        max_sum = 0\n",
    "        right = len(nums1)-1\n",
    "        cnt = k\n",
    "        while cnt > 0:\n",
    "            heapq.heappush(heap,cap[right][0])\n",
    "            max_sum += cap[right][0]\n",
    "            right -= 1\n",
    "            cnt -= 1\n",
    "        # print(heap,right)\n",
    "        res = max_sum*cap[right+1][1]\n",
    "        while right >= 0:\n",
    "            max_sum += cap[right][0]\n",
    "            heapq.heappush(heap,cap[right][0])\n",
    "            max_sum -= heapq.heappop(heap)\n",
    "            res = max(res,max_sum*cap[right][1])\n",
    "            right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pair = list(zip(nums2,nums1))\n",
    "        pair.sort(reverse=True)\n",
    "\n",
    "        res=0\n",
    "        total=0\n",
    "        heap=[]\n",
    "\n",
    "        for i in pair:\n",
    "            total += i[1]\n",
    "            heapq.heappush(heap, i[1])\n",
    "\n",
    "            if k<len(heap):\n",
    "                total -=heapq.heappop(heap)\n",
    "\n",
    "            if k==len(heap):\n",
    "                res = max(res, total*i[0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        # Min Heap\r\n",
    "        - 對 nums2 由大到小排序，確保每取k個數字時，其中最小的數字是最後一個數\r\n",
    "        - 因此初始化答案為 nums2[:k] 的和乘上 nums2[k-1] (最小的數字)\r\n",
    "        - 接著考慮每次更新的n1, n2，\r\n",
    "            - 若 n1 <= heap.top (即目前所選數中的最小值)，因為 n2 是 遞減的，故不會影響答案\r\n",
    "            - 若 n1 > heap.top，則更新 heap，並更新答案\r\n",
    "    \"\"\"\r\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\r\n",
    "        nums = sorted(zip(nums1, nums2), key=lambda x: x[1], reverse=True)\r\n",
    "        hp = [num for num, _ in nums[:k]]\r\n",
    "        heapq.heapify(hp)\r\n",
    "        cur = sum(hp)\r\n",
    "        ans = cur * nums[k-1][1] # nums[k-1][1] is the smallest number in nums2[:k]\r\n",
    "        for n1, n2 in nums[k:]:\r\n",
    "            if n1 > hp[0]:\r\n",
    "                cur += n1\r\n",
    "                cur -= heapq.heapreplace(hp, n1)\r\n",
    "                ans = max(ans, cur * n2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums3 = sorted(zip(nums1, nums2), reverse = True, key = lambda x:x[1])\n",
    "        heap = [x for x, _ in nums3[:k]]\n",
    "        sums = sum(heap)\n",
    "        output = sums * nums3[k - 1][1]\n",
    "        heapify(heap) # 这一步不能省！不然第一次判断x > heap[0]时heap[0]不一定是最小的！\n",
    "        for x, y in nums3[k:]:\n",
    "            if (x > heap[0]): # 如果存在更大的可能性\n",
    "                sums += x - heapreplace(heap, x) # 那就删除堆顶后将新元素放到堆顶并下沉\n",
    "                output = max(output, sums * y)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = sorted(zip(nums1,nums2),key = lambda x: x[1])\n",
    "        n = len(nums)\n",
    "        # 初始化一个大小为k的堆\n",
    "        heap = [item[0] for item in nums[-k:]]\n",
    "        heapify(heap)\n",
    "        sm = sum(heap)\n",
    "        ans = 0\n",
    "        ans = max(ans,sm*nums[-k][1])\n",
    "        # 由于会用到[i,n]中的最小数，所以应该反向递推\n",
    "        # sm = sum(heap)\n",
    "        # for i in range(len(nums)):\n",
    "        #     n1 = nums[i][0]\n",
    "        #     n2 = nums[i][1]\n",
    "        #     for j in range(k,len(nums)):\n",
    "        #         heappushpop()\n",
    "        for i in range(n-k-1,-1,-1):\n",
    "            # 更新堆，记录乘积\n",
    "            item = heappushpop(heap,nums[i][0])\n",
    "            sm = sm - item + nums[i][0]\n",
    "            ans = max(ans,sm*nums[i][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        # sort by nums2\n",
    "        nums=[(nums1[i],nums2[i]) for i in range(len(nums1))]\n",
    "        nums.sort(key=lambda x:x[1])\n",
    "        nums1=[num[0] for num in nums]\n",
    "        nums2=[num[1] for num in nums]\n",
    "        # loop, min2 is nums2[i], max1 is max of nums1[i:],i in (0,len-k)\n",
    "        max1=[0 for _ in range(len(nums1)-k+1)]\n",
    "        min2=nums2[:len(nums2)-k+1]\n",
    "        current_max_sub=nums1[-k:]\n",
    "        heapq.heapify(current_max_sub)\n",
    "        max1[-1]=sum(current_max_sub)\n",
    "        for i in range(len(nums1)-k-1,-1,-1):\n",
    "            # select k largest from nums1[i:]\n",
    "            # update: calculate all max in one loop\n",
    "            # loop from right to left, initial nums1[-k:]\n",
    "            heapq.heappush(current_max_sub,nums1[i])\n",
    "            max1[i]=max1[i+1]+nums1[i]#+=nums1[i]\n",
    "            max1[i]-=heapq.heappop(current_max_sub)#-=minimum\n",
    "        answer=max(max1[i]*min2[i] for i in range(len(max1)))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        sortedPair = []\n",
    "        for i in range(len(nums1)):\n",
    "            sortedPair.append([nums1[i], nums2[i]])\n",
    "        sortedPair = sorted(sortedPair, key = lambda pair: pair[1], reverse=True)\n",
    "\n",
    "        heap = [x[0] for x in sortedPair[:k]]\n",
    "        heapify(heap)\n",
    "        s = sum(heap)\n",
    "        maxVal = s * sortedPair[k-1][1]\n",
    "        for x, y in sortedPair[k:]:\n",
    "            if x > heap[0]:\n",
    "                s += x - heappushpop(heap, x)\n",
    "                maxVal = max(maxVal, (s * y))\n",
    "        \n",
    "        return maxVal\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = sorted(zip(nums2,nums1),reverse=True)\n",
    "        print(nums)\n",
    "        heap = []\n",
    "        #i = 0\n",
    "        #j = 1\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i != 0:     \n",
    "                heapq.heappush(heap,nums[i-1][1])\n",
    "                s += nums[i-1][1]\n",
    "            if i >= k:\n",
    "                s -= heap[0]\n",
    "                heapq.heappop(heap)\n",
    "            #print(i,s,(s+nums[i][1])*nums[i][0])\n",
    "            if i >= k - 1:\n",
    "                ans = max(ans, (s+nums[i][1])*nums[i][0])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        nums = []\n",
    "        for n1, n2 in zip(nums1, nums2):\n",
    "            nums.append([n2, n1])\n",
    "        nums.sort(key = lambda x: x[0])\n",
    "        res = 0; sums = 0; heap = []\n",
    "        for i in range(len(nums)-1, len(nums)-k, -1):\n",
    "            sums += nums[i][1]\n",
    "            heapq.heappush(heap, nums[i][1])\n",
    "        res = (sums + nums[len(nums)-k][1])*nums[len(nums)-k][0]\n",
    "        for i in range(len(nums) - k - 1, -1, -1):\n",
    "            temp = heapq.heappushpop(heap, nums[i + 1][1])\n",
    "            sums = sums + nums[i+1][1] - temp\n",
    "            res = max(res, nums[i][0] * (sums + nums[i][1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = []\n",
    "        result = 0\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append([nums2[i] , nums1[i]])\n",
    "        nums.sort(key=lambda x:x[0] , reverse= True)\n",
    "        tmpheap = []\n",
    "        tmpsum = 0\n",
    "        for i in range(k-1):\n",
    "            heapq.heappush(tmpheap , nums[i][1])\n",
    "            tmpsum = tmpsum + nums[i][1]\n",
    "        for i in range(k-1 , len(nums)):\n",
    "            heapq.heappush(tmpheap , nums[i][1])\n",
    "            tmpsum = tmpsum + nums[i][1]\n",
    "            if len(tmpheap) > k:\n",
    "                tmp1 = heapq.heappop(tmpheap)\n",
    "                tmpsum = tmpsum - tmp1\n",
    "            tmp = tmpsum * nums[i][0]\n",
    "            if tmp > result:\n",
    "                result = tmp\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = [[nums1[i], nums2[i]] for i in range(len(nums1))]\n",
    "        nums = sorted(nums, key=lambda x: x[1], reverse=True)\n",
    "        # print(nums, k)\n",
    "        minHeap = [nums[i][0] for i in range(k)]\n",
    "        heapq.heapify(minHeap)\n",
    "        nsum = sum(minHeap)\n",
    "        maxNum = nsum*nums[k-1][1]\n",
    "        for i in range(k, len(nums)):\n",
    "            top = minHeap[0]\n",
    "            if nums[i][0]>top:\n",
    "                nsum = nsum-top+nums[i][0]\n",
    "                heapq.heapreplace(minHeap,nums[i][0])\n",
    "                tmp = nsum * nums[i][1]\n",
    "                if tmp > maxNum:\n",
    "                    maxNum = tmp\n",
    "        return maxNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = [[nums1[x], nums2[x]] for x in range(n)]\n",
    "        nums.sort(key = lambda y: y[1], reverse = True)\n",
    "        heap = [x for x, _ in nums[:k]]\n",
    "        # 初始化\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        for i in range(k):\n",
    "            total += nums[i][0]\n",
    "        heapq.heapify(heap)\n",
    "        ans = total * nums[k-1][1]\n",
    "        # 变换\n",
    "        for i in range(k, n):\n",
    "            if nums[i][0] > heap[0]:\n",
    "                total -= heapq.heappop(heap)\n",
    "                total += nums[i][0]\n",
    "                ans = max(ans, total * nums[i][1])\n",
    "                heapq.heappush(heap, nums[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: -p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k - 1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n, hp, sm, ans = len(nums1), [], 0, 0\n",
    "        for i in sorted(range(n), key = lambda i: -nums1[i]):\n",
    "            if len(hp) < k:\n",
    "                sm += nums1[i]\n",
    "                heapq.heappush(hp, (nums2[i], i))\n",
    "            elif nums2[i] > hp[0][0]:\n",
    "                sm += nums1[i] - nums1[hp[0][1]]\n",
    "                heapq.heapreplace(hp, (nums2[i], i))\n",
    "            if (len(hp) == k):\n",
    "                ans = max(ans, sm * hp[0][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        c = defaultdict(list)\n",
    "        s = set()\n",
    "        for i, x in enumerate(nums2):\n",
    "            c[x].append(i)\n",
    "            s.add(x)\n",
    "        s = list(s)\n",
    "        s.sort()\n",
    "        s = s[::-1]\n",
    "        h = []\n",
    "        cnt = 0 \n",
    "        \n",
    "        ans = -inf\n",
    "        pre = 0\n",
    "        pre_cnt = 0\n",
    "        \n",
    "        for x in s:\n",
    "            for i in c[x]:\n",
    "                heappush(h, nums1[i])\n",
    "                pre += nums1[i]\n",
    "                if len(h) == k:\n",
    "                    ans = max(ans, pre*x)\n",
    "                if len(h) > k:\n",
    "                    pre -= heappop(h)\n",
    "                    ans = max(ans, pre*x)\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        num_sort = list(zip(nums2, nums1))\n",
    "        num_sort.sort()\n",
    "        n = len(nums1)\n",
    "        max_sum = [0] * n\n",
    "        t_sum = 0\n",
    "        mem = []\n",
    "        for i in range(n-1, n-k-1, -1):\n",
    "            heapq.heappush(mem, num_sort[i][1])\n",
    "            t_sum += num_sort[i][1]\n",
    "        max_sum[n-k] = t_sum\n",
    "        for i in range(n-k-1, -1, -1):\n",
    "            heapq.heappush(mem, num_sort[i][1])\n",
    "            tv = heapq.heappop(mem)\n",
    "            t_sum += num_sort[i][1] - tv\n",
    "            max_sum[i] = t_sum\n",
    "        # print(max_sum)\n",
    "        # print(num_sort)\n",
    "        max_res = 0\n",
    "        for i in range(n-k+1):\n",
    "            max_res = max(max_res, max_sum[i]*num_sort[i][0])\n",
    "        \n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        vs = [(v1, v2) for v1, v2 in zip(nums1, nums2)]\n",
    "        vs.sort(key=lambda v: v[1])\n",
    "        arr1 = [i for i, j in vs]\n",
    "        if k == 1:\n",
    "            return max([i * j for i, j in vs])\n",
    "        arr_t = arr1[1-k:]\n",
    "        heapq.heapify(arr_t)\n",
    "\n",
    "        sum_max = deque() # \n",
    "        sum_max.append(\n",
    "            sum(arr_t)\n",
    "        )\n",
    "        rst = (sum_max[0] + arr1[-k]) * vs[-k][1]\n",
    "\n",
    "        for i in range(k, len(nums1)):\n",
    "            pre_sum = sum_max[0]\n",
    "            rm_v = heapq.heappushpop(arr_t, arr1[-i])\n",
    "            sum_max.appendleft(\n",
    "                pre_sum - rm_v + arr1[-i] \n",
    "            )\n",
    "            rst = max(rst, (sum_max[0] + arr1[-i - 1]) * vs[-i - 1][1])\n",
    "        return rst\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        vs = [(v1, v2) for v1, v2 in zip(nums1, nums2)]\n",
    "        vs.sort(key=lambda v: v[1])\n",
    "        arr1 = [i for i, j in vs]\n",
    "        if k == 1:\n",
    "            return max([i * j for i, j in vs])\n",
    "        arr_t = arr1[1-k:]\n",
    "        heapq.heapify(arr_t)\n",
    "\n",
    "        sum_max = deque() # \n",
    "        sum_max.append(\n",
    "            sum(arr_t)\n",
    "        )\n",
    "        rst = (sum_max[0] + arr1[-k]) * vs[-k][1]\n",
    "\n",
    "        for i in range(k, len(nums1)):\n",
    "            pre_sum = sum_max[0]\n",
    "            rm_v = heapq.heappushpop(arr_t, arr1[-i])\n",
    "            sum_max.appendleft(\n",
    "                pre_sum - rm_v + arr1[-i] \n",
    "            )\n",
    "            rst = max(rst, (sum_max[0] + arr1[-i - 1]) * vs[-i - 1][1])\n",
    "        return rst\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: -p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k - 1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        minHeap = []    # min-heap, element: num1\n",
    "        num1Sum = 0\n",
    "        # 1. O(NlogN) sort tuple arrays (speed[i], efficiency[i]) by efficiency[i] descendingly\n",
    "        tuples = sorted(zip(nums1, nums2), key=lambda x: -x[1])\n",
    "\n",
    "        # 2. O(nlogk) iterate over sorted tuple arrays\n",
    "        for num1, num2 in tuples:\n",
    "            heappush(minHeap, num1)\n",
    "            if len(minHeap) > k:    # at most k engineers\n",
    "                num1Sum -= heappop(minHeap)\n",
    "            num1Sum += num1 \n",
    "            if len(minHeap) == k:\n",
    "                ans = max(ans, num1Sum * num2)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: -p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k - 1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p:-p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k - 1][1]\n",
    "        for x,y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        from heapq import heapify, heapreplace\n",
    "\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: -p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        res = s * a[k-1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if (gap := x - h[0]) > 0:\n",
    "                heapreplace(h, x)\n",
    "                s += gap\n",
    "                res = max(res, s*y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: -p[1])\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k - 1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = sorted(zip(nums1, nums2), key=lambda x: -x[1])\n",
    "        h = [i for i, _ in nums[:k]]\n",
    "        heapq.heapify(h)\n",
    "        s = sum(h)\n",
    "        res = s * nums[k-1][1]\n",
    "        for x, y in nums[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapq.heapreplace(h, x)\n",
    "                res = max(res, s*y)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        arr = [(x, y) for x, y in zip(nums2, nums1)]       \n",
    "        arr.sort()\n",
    "        f = [0] * n\n",
    "        h = []\n",
    "        cur = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur += arr[i][1]\n",
    "            heappush(h, arr[i][1])\n",
    "            if len(h) > k:\n",
    "                cur -= heappop(h)\n",
    "            f[i] = cur\n",
    "        res = 0\n",
    "        for i, (a, b) in enumerate(arr):\n",
    "            if i + k > n: break\n",
    "            res = max(res, a * f[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pair_list = [(x1, x2) for x1, x2 in zip(nums1, nums2)]\n",
    "        pair_list = sorted(pair_list, key=lambda x: x[1])[::-1]\n",
    "\n",
    "        heap = list()\n",
    "\n",
    "        for i in range(k):\n",
    "            heap.append(pair_list[i][0])\n",
    "\n",
    "        res = sum(heap) * pair_list[k-1][1]\n",
    "\n",
    "        heapq.heapify(heap)\n",
    "        s = sum(heap)\n",
    "\n",
    "        for i in range(k, len(pair_list)):\n",
    "            n1, n2 = pair_list[i]\n",
    "\n",
    "            s = s - heap[0] + n1\n",
    "            heapq.heappop(heap)\n",
    "            heapq.heappush(heap, n1)\n",
    "\n",
    "            new_res = s * n2\n",
    "\n",
    "            if new_res > res:\n",
    "                res = new_res\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        arr = [(-n2, n1) for n1, n2 in zip(nums1, nums2)]\n",
    "        arr.sort()\n",
    "        print(arr)\n",
    "\n",
    "        n = len(arr)\n",
    "        hp=[]\n",
    "        for i in range(k):\n",
    "            heappush(hp, arr[i][1])\n",
    "\n",
    "        summ = sum(hp)\n",
    "        print(summ)\n",
    "        res = -arr[k-1][0]*summ\n",
    "        for i in range(k, n):\n",
    "            minN1 = heappop(hp)\n",
    "            heappush(hp, arr[i][1])\n",
    "            summ += arr[i][1]-minN1\n",
    "            res = max(res, -arr[i][0]*summ)\n",
    "        return res\n",
    "\n",
    "\n",
    "# res = 17*7 = 119\n",
    "# 6*28 = 168\n",
    "\n",
    "\n",
    "# (13,14)(11,2)(7,1)(6,12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return max([n1*n2 for n1, n2 in zip(nums1, nums2)])\n",
    "        if k == len(nums1):\n",
    "            return sum(nums1) * min(nums2)\n",
    "        \n",
    "        a = sorted(zip(nums1, nums2), key=lambda p: p[1], reverse=True)\n",
    "        h = [x for x, _ in a[:k]]\n",
    "        heapq.heapify(h)\n",
    "        s = sum(h)\n",
    "        ans = s * a[k-1][1]\n",
    "        for x, y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x - heapq.heapreplace(h, x)\n",
    "                ans = max(ans, s * y)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        pq1 = []\n",
    "        pq2 = [(num, i) for i, num in enumerate(nums2)]\n",
    "        set1 = set(nums1)\n",
    "        pq2.sort(reverse=True)\n",
    "        sm = 0\n",
    "        for i in range(k):\n",
    "            minn, j = pq2[i]\n",
    "            heapq.heappush(pq1, nums1[j])\n",
    "            sm += nums1[j]\n",
    "        res = sm * minn\n",
    "        for i in range(k, len(nums2)):\n",
    "            minn, j = pq2[i]\n",
    "            top = heapq.heappop(pq1)\n",
    "            heapq.heappush(pq1, nums1[j])\n",
    "            sm = sm + nums1[j] - top\n",
    "            res = max(res, sm * minn)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        l = sorted(list(zip(nums2, nums1)), key=lambda x: -x[0])\n",
    "        print(l)\n",
    "\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        heap = []\n",
    "\n",
    "        for n1, n2 in l[:k]:\n",
    "            heappush(heap, n2)\n",
    "            s += n2\n",
    "\n",
    "        ans = s * n1\n",
    "        for n1, n2 in l[k:]:\n",
    "            s -= heappop(heap)\n",
    "            \n",
    "            heappush(heap, n2)\n",
    "            s += n2\n",
    "            ans = max(ans, s * n1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        l = sorted(list(zip(nums2, nums1)), key=lambda x: -x[0])\n",
    "        print(l)\n",
    "\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        heap = []\n",
    "\n",
    "        for n1, n2 in l[:k]:\n",
    "            heappush(heap, n2)\n",
    "            s += n2\n",
    "\n",
    "        ans = s * n1\n",
    "        for n1, n2 in l[k:]:\n",
    "            s -= heappop(heap)\n",
    "            \n",
    "            heappush(heap, n2)\n",
    "            s += n2\n",
    "            ans = max(ans, s * n1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pair = []\n",
    "        for i in range(len(nums1)):\n",
    "            pair.append([nums1[i], nums2[i]])\n",
    "        pair.sort(key=lambda x: -x[1])\n",
    "        sub_sum = 0\n",
    "        result = 0\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        for i in range(k-1):\n",
    "            sub_sum += pair[i][0]\n",
    "            heapq.heappush(pq, pair[i][0])\n",
    "        for i in range(k-1, len(pair)):\n",
    "            heapq.heappush(pq, pair[i][0])\n",
    "            sub_sum += pair[i][0]\n",
    "            result = max(result, sub_sum * pair[i][1])\n",
    "            el = heapq.heappop(pq)\n",
    "            sub_sum -= el\n",
    "        return result\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(nums1, nums2), key=lambda x: -x[1])\n",
    "        h = [x for x,_ in a[:k]]\n",
    "        s = sum(h)\n",
    "        heapq.heapify(h)\n",
    "        print(a)\n",
    "        ans = s*a[k-1][1]\n",
    "        for x,y in a[k:]:\n",
    "            if x > h[0]:\n",
    "                s += x-heapq.heapreplace(h, x)\n",
    "                ans = max(ans, s*y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n=len(nums1)\n",
    "        nums=[[nums1[i],nums2[i]] for i in range(n)]\n",
    "        nums.sort(key=lambda x:-x[1])\n",
    "        que=[]\n",
    "        cursum=0\n",
    "        for i in range(k):\n",
    "            heapq.heappush(que,(nums[i][0]))\n",
    "            cursum+=nums[i][0]\n",
    "        res=cursum*nums[k-1][1]\n",
    "        for i in range(k,n):\n",
    "            pre=que[0]\n",
    "            if nums[i][0]>pre:\n",
    "                cursum+=nums[i][0]-pre\n",
    "                heapq.heappop(que)\n",
    "                heapq.heappush(que,(nums[i][0]))\n",
    "                res=max(res,cursum*nums[i][1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = [[num1, num2] for num1, num2 in zip(nums1, nums2)]\n",
    "        n = len(nums)\n",
    "        nums.sort(key = lambda x:-x[1])\n",
    "        tsum = 0\n",
    "        heap = []\n",
    "        for i in range(k):\n",
    "            heappush(heap, nums[i][0])\n",
    "            tsum += nums[i][0]\n",
    "        result = tsum*nums[k-1][1]\n",
    "        for i in range(k,n):\n",
    "            num1, num2 = nums[i]\n",
    "            if(num1 > heap[0]):\n",
    "                tsum = tsum - heap[0] + num1\n",
    "                heapreplace(heap, num1)\n",
    "            result = max(result, tsum*num2)\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = [[num1, num2] for num1, num2 in zip(nums1, nums2)]\n",
    "        n = len(nums)\n",
    "        nums.sort(key = lambda x:-x[1])\n",
    "        tsum = 0\n",
    "        heap = []\n",
    "        for i in range(k):\n",
    "            heappush(heap, nums[i][0])\n",
    "            tsum += nums[i][0]\n",
    "        result = tsum*nums[k-1][1]\n",
    "        for i in range(k,n):\n",
    "            num1, num2 = nums[i]\n",
    "            if(num1 > heap[0]):\n",
    "                tsum = tsum - heap[0] + num1\n",
    "                heapreplace(heap, num1)\n",
    "            result = max(result, tsum*num2)\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "import heapq\n",
    "class Solution:\n",
    "    def compare(self, a, b):  \n",
    "        if a[1] >= b[1]:\n",
    "            return -1\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = []\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append((nums1[i], nums2[i]))\n",
    "        ### 根据 nums2 从大到小排序\n",
    "        nums = sorted(nums, key=cmp_to_key(self.compare)) \n",
    "        ss = []\n",
    "        sum, res = 0, 0\n",
    "        for i in range(k):\n",
    "            heapq.heappush(ss, nums[i][0])  ## 最小值堆\n",
    "            sum += nums[i][0]\n",
    "        res = max(res, sum*nums[k-1][1])\n",
    "        ## 往右遍历时, 最小值会一直变小, 故只有sum 变大时才可能会更新 res\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i][0] > ss[0]:\n",
    "                sum += nums[i][0] - ss[0]\n",
    "                heapq.heappop(ss)\n",
    "                heapq.heappush(ss, nums[i][0])\n",
    "                res = max(res, sum*nums[i][1])\n",
    "        return res\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = [(n1,n2) for n1,n2 in zip(nums1,nums2)]\n",
    "        nums.sort(key=lambda x:-x[1])\n",
    "        hp = []\n",
    "        ret = 0\n",
    "        s = 0\n",
    "        for n1,n2 in nums:\n",
    "            if len(hp) < k:\n",
    "                heappush(hp,(n1,n2))\n",
    "                s += n1\n",
    "                ret = n2 * s\n",
    "            else:\n",
    "                if hp[0][0] < n1:\n",
    "                    nret = n2 * (s + n1 - hp[0][0])\n",
    "                    ret = max(ret,nret)\n",
    "                    s += n1 - hp[0][0]\n",
    "                    heappop(hp)\n",
    "                    heappush(hp,(n1,n2))\n",
    "        return ret\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums1)\n",
    "        nums = list(zip(nums1,nums2))\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        v = 0\n",
    "        l = 0\n",
    "        stack = []\n",
    "        for r , (num , min_val) in enumerate(nums):\n",
    "            v += num\n",
    "            heapq.heappush(stack,(min_val,num))\n",
    "            if r - l + 1 > k:\n",
    "                v -= heapq.heappop(stack)[1]\n",
    "                l += 1\n",
    "            if r - l + 1 == k:\n",
    "                ans = max(ans,v*stack[0][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ##########################################\n",
    "    ############ see also 1383 ################\n",
    "    ##########################################\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        \n",
    "        # combined sequence, sorted by nums2 from large to small\n",
    "        nums3 = sorted(zip(nums1, nums2), key = lambda x: -x[1])\n",
    "        h = []\n",
    "        sums = 0\n",
    "        mins = nums3[k-1][1]\n",
    "\n",
    "        for (i, j) in nums3[:k]:\n",
    "            heapq.heappush(h, (i,j))\n",
    "            sums += i\n",
    "        ans = sums * j\n",
    "\n",
    "        # replace only if i is larger for (i,j) in nums3[k:], since j is always no larger than current min.\n",
    "        for (i, j) in nums3[k:]:\n",
    "            if i > h[0][0]:\n",
    "                out_i, _ = heapq.heappushpop(h, (i, j))\n",
    "                sums = sums - out_i + i\n",
    "                ans = max(ans, sums*j)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        nums = []\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append((nums1[i], nums2[i]))\n",
    "        nums = sorted(nums)\n",
    "        nums.reverse()   ##  根据 nums1 中的元素从大到小排序\n",
    "        ss = []\n",
    "        curSum = 0\n",
    "        for i in range(k):\n",
    "            curSum += nums[i][0]\n",
    "            heapq.heappush(ss, (nums[i][1], nums[i][0]))   ## 最小值堆\n",
    "        res = curSum * ss[0][0]\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i][1] > ss[0][0]:\n",
    "                curSum += - ss[0][1] + nums[i][0]\n",
    "                heapq.heappop(ss)\n",
    "                heapq.heappush(ss, (nums[i][1], nums[i][0]))\n",
    "                res = max(res, curSum*ss[0][0])\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
